二分搜索算法

Ac_c0mpany丶 2021-08-15 13:42:53 阅读数:235

本文一共[544]字,预计阅读时长:1分钟~
二分 搜索算法 搜索 算法

二分搜索算法

常用的使用場景:尋找一個數,尋找左側邊界,尋找右側邊界

1.1 二分搜索模板

先介紹下二分搜索模板,後面的二分搜索都是基於這個二分搜索模板的

int binarySearch(vector<int>& nums, int target){
int left = 0, right = ...; // right = nums.size() 還是 right = nums.size() - 1
while(...){ // left < right 還是 left <= right
int mid = left + (right - left) / 2; //防止溢出 mid = (left + right) / 2;可能出現溢出
if(nums[mid] == target) ... ;
else if(nums[mid] < target) left = ... ;
else if(nums[mid] > target) right = ... ;
}
return ...;
}

說明:

  1. 分析二分搜索代碼時,不要出現else,全部展開成else if,方便理解
  2. ...的地方是需要詳細說明的細節
  3. mid = (left + right) / 2 可能出現溢出, 為了防止溢出 mid = left + (right - left) / 2;

1.2 尋找一個數(基本的二分搜索)

場景:搜索一個數,如果存在,則返回索引,否則返回-1

在此之前,先簡單提下搜索區間這個概念,二分搜索的變形一般分有左閉右閉左閉右開兩種搜索區間

左閉右閉區間
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size() - 1; //注意 right
while(left <= right){ //注意 <=
int mid = mid = left + (right - left) / 2;
if(nums[mid] == traget) return mid;
else if(nums[mid] < target) left = mid + 1; // 注意
else if(nums[mid] > target) right = mid - 1; // 注意
}
return -1;
}

首先 leftright 指針 分別指向數組的首尾元素,都是可以取到的,我們稱這個二分的搜索區間為左閉右閉區間,即[left, right],這個區間其實就是每次進行搜索的區間,那麼當區間為空的時候就終止搜索,那麼啥時候區間剛好終止呢?答案是left = right + 1的時候,區間變為[right + 1, right],這個區間為空。舉個例子[2, 2]區間還存在數字2,而[3, 2]這個區間是不存在的。所以while的循環條件應該是left <= right,其終止條件正好是left == right + 1,區間為空(而不是left < right,它的終止條件是left == right 區間非空)。下面開始搜索mid是否為查找的目標值,是就返回mid,不是就應該去掉mid分割成兩個區間,而且應該保證這兩個區間也是左閉右閉區間,那麼只有分成[left, mid - 1] 和 [mid + 1, right]兩種,這也就確定了後面left 和 right 的更新。當沒搜索到目標值時,返回-1;

左閉右開區間
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size(); //注意 right
while(left < right) { //注意 <
int mid = mid = left + (right - left) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) left = mid + 1; // 注意
else if(nums[mid] > target) right = mid; //注意
}
//while循環的終止條件 left == right
return -1;
}

首先 leftright 指針 分別指向數組的首元素和末尾元素的後一比特,顯然right是取不到數組中元素的,我們稱這個二分搜索區間為左閉右開區間, 即[left ,right),這個區間其實就是每次進行搜索的區間,那麼當區間為空的時候就終止搜索,那麼啥時候區間剛好終止呢?答案是當left == right的時候,舉個例子區間[2, 2)顯然不存在。所以while循環條件應該是left < right,其終止條件正好是left == right,區間為空(為啥不是<=呢, 因為此時不是臨界條件,不滿足剛好停止)。下面開始搜索mid是否為查找的目標值,是就返回mid,不是就應該去掉mid分割成兩個區間,而且應該保證這兩個區間也是左閉右開區間,那麼只有分割成[left,mid) 和 [mid + 1,right),這也就確定了後面left 和 right 的更新。當沒搜索到目標值時,返回-1;

但是上面兩種算法存在局限性,比如,提供有序數組nums = [1, 3, 3, 3, 4],target = 3,則該算法返回的是正中間的索引2。但是如果我們想找到target的左側邊界,即索引1,或者想找到target的右側邊,即索引3,則算法是無法處理的,下面就介紹算法的改進

1.3 尋找左側邊界的二分搜索

提供兩種寫法

左閉右閉區間
int left_bound(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size() - 1; //左閉右閉區間[left, right]
while(left <= right){ //循環終止條件left == right + 1, [right + 1, right]區間為空
int mid = mid = left + (right - left) / 2;
if(nums[mid] == target) right = mid - 1; // 注意
else if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid - 1;
}
// while 循環退出的條件 left == right + 1
// 當target比nums中所有元素大時,left會索引越界
// 當target比nums中所有元素小時,right會索引越界,left剛好指向第一個元素
// 當target不在數組中,且不滿足上述兩種情况,則left會指向某個元素,其索引為x,其特殊含義是nums中小於target的元素有x個
if(left == nums.size() || nums[left] != target) return -1;
return left; //其特殊含義是nums中小於target的元素有left個
}

說明:

  1. 能搜索左側邊界的關鍵在於if(nums[mid] == target) right = mid - 1; ,找到target時不要立即返回,而是縮小搜索區間的上界right,在區間[left ,mid - 1]中繼續搜索,即不斷向左搜索,達到搜索左側邊界的目的
  2. left 和 right 的更新 思路 關鍵在於把握區間的切割,保證切割後的兩個區間也是左閉右閉的
  3. left的含義是nums中小於target的元素有left個,所以left的取值範圍[0, nums.size()],所以當left == nums.size() 或者nums[left] != target時,錶示未找到target,返回-1;否則錶示找到,left所指即為答案。
左閉右開區間
int left_bound(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size(); //左閉右開區間[left,right)
while(left < right){ //循環終止條件left == right [right, right)區間為空
int mid = left + (right - left) / 2;
if(nums[mid] == target) right = mid; // 注意
else if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid;
}
//循環退出的條件是 left == right
if(left == nums.size() || nums[left] != target) return -1;
return left;//其特殊含義是nums中小於target的元素有left個
}

說明:

  1. 當找到target值時,不要立即返回,縮小區間的上界,在區間[left, mid)中繼續搜索,所以更新right = mid

1.4 尋找右側邊界的二分搜索

提供兩種寫法

左閉右閉區間
int right_bound(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size() - 1; //左閉右閉區間
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target) left = mid + 1; //注意
else if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid - 1;
}
//最後檢查right越界情况
if(right < 0 || nums[right] != target) return -1;
return right;
}
左閉右開區間
int right_bound(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size(); //左閉右開區間
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] == target) left = mid + 1; //注意
else if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid;
}
//注意:因為對left的更新必須是left = mid + 1,也就是說while循環終止時,nums[left]一定不等於target了,而nums[left - 1]可能等於target
if(left == 0) return -1;
return nums[left - 1] == target ? (left - 1) : -1;
}

左閉右開區間搜索右側邊界時,需要减1

1. 5 二分搜索模板統一

對於尋找左右邊界的二分搜索,常見的方式是使用左閉右開的搜索區間,為了便於記憶,全部統一為左閉右閉區間

int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = mid = left + (right - left) / 2;
if(nums[mid] == traget) return mid; // 直接返回
else if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid - 1;
}
// 直接返回
return -1;
}
int left_bound(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = mid = left + (right - left) / 2;
if(nums[mid] == target) right = mid - 1; // 固定左邊界,收縮右邊界
else if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid - 1;
}
// 最後檢查left越界的情况
if(left == nums.size() || nums[left] != target) return -1;
return left;
}
int right_bound(vector<int>& nums, int target){
if(nums.size() == 0) return -1;
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target) left = mid + 1; // 固定右邊界,收縮左邊界
else if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid - 1;
}
//最後檢查right越界情况
if(right < 0 || nums[right] != target) return -1;
return right;
}
版权声明:本文为[Ac_c0mpany丶]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815134249969v.html