前言

????????在算法競賽中，二分查找使用的頻率是非常高的，對于C++選手而言，有STL中自帶的lower_bound和upper_bound二分查找，可以很方便的進行二分查找。但是非C++選手、或者需要自定義多條件查找的情況需要自己寫一個二分，本文對幾種常見的二分查找寫法進行講解。

????????本文使用的編程語言為Java，但代碼比較好理解其他語言選手也可以查看本文來學習二分相關內容。

---

二分查找

????????二分查找，也稱折半查找，是一種可以在有序序列上進行快速查找的算法，時間復雜度是O(logn)。

????????常見的二分查找類型，有以下兩種：

• 查找目標值在序列中不小于目標值的第一個元素（同lower_bound，以此查到第一個位置）。

• 查找目標值在序列中第一個大于目標值的元素（同upper_bound，以此查找到最后一個出現的位置）。

????????在設置區間的時候，根據寫法的不同分為下面幾種：

• 左閉右閉。

• 左閉右開。

????????根據最終獲取答案的寫法，又分為下面兩種：

• 在左右指針處取值。

• 設置額外變量取值。

????????本文將分不同情況，寫出不同情況下的二分查找模板，幫助大家理解學習。

---

查找目標值在序列中不小于目標值的第一個元素

????????也就是實現一個STL中的lower_bound。

左閉右閉版

/*** [l,r]左閉右閉區間 lower_bound* @param nums 遞增序列* @param target 目標值* @return 返回不小于目標值的第一個元素下標*/
int lowBs(int[] nums,int target){int l=0;int r=nums.length-1;while(l<=r){int mid=l+(r-l>>1);if(nums[mid]<target){l=mid+1;}else{r=mid-1;}}return l;
}

左閉右開版

/*** [l,r)左閉右閉區間 lower_bound* @param nums 遞增序列* @param target 目標值* @return 返回不小于目標值的第一個元素下標*/
int lowBs(int[] nums,int target){int l=0;int r=nums.length;while(l<r){int mid=l+(r-l>>1);if(nums[mid]<target){l=mid+1;}else{r=mid;}}return l;
}

---

查找目標值在序列中第一個大于目標值的元素

????????也就是實現一個STL中的upper_bound。

左閉右閉版

/***  [l,r]左閉右閉 upper_bound* @param arr 遞增序列* @param target 目標值* @return 返回第一個大于目標值的位置*/
int highBs(int[] arr,int target){int l=0;int r=arr.length - 1;while(l<=r){int mid=l+(r-l>>1);if(arr[mid]<=target){l=mid+1;}else{r=mid-1;}}return l;
}

左閉右開版

/***  [l,r)左閉右開 upper_bound* @param arr 遞增序列* @param target 目標值* @return 返回第一個大于目標值的位置*/
int highBs(int[] arr,int target){int l=0;int r=arr.length;while(l<r){int mid=l+(r-l>>1);if(arr[mid]<=target){l=mid+1;}else{r=mid;}}return l;
}

---

易錯問題和常見問題總結

一、需要注意區間定義和終止條件是否匹配正確

• 左閉右閉：初始化 r = nums.length-1，終止條件 while (l <= r)。

• 左閉右開：初始化 r = nums.length，終止條件 while (l < r)。

二、指針更新是否正確

• 左閉右閉：r = mid - 1 或 l = mid + 1。

• 左閉右開：r = mid。

三、運算符優先級

????????應寫為：int mid = l + ( r - l >> 1)

？為什么不能寫為 l + r >> 1

????????如果可以保證l+r不會溢出的話，其實這樣寫也可以，但是為了保證不出現數據溢出，更加推薦寫上面的形式。