寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.二分查找簡介
2.基本二分搜索
???? ?? 基本二分搜索簡介
???? ?? LeetCode 69.x的平方根
???? ?? LeetCode 374.猜數字大小
???? ?? LeetCode 33.搜索旋轉排序數組
3.尋找左側邊界的二分搜索
???? ?? 尋找左側邊界的二分搜索簡介
???? ?? LeetCode 278.第一個錯誤的版本
???? ?? LeetCode 162.尋找峰值
???? ?? LeetCode 153. 尋找旋轉排序數組中的最小值
4.尋找右側邊界的二分查找
???? ?? 尋找右側邊界的二分查找簡介
???? ?? LeetCode34.在排序數組中查找元素的第一個和最后一個位置
???? ??

1.二分查找

二分查找法（Binary Search）算法，也叫折半查找算法。二分查找針對的是一個有序(如果集合是無序的，我們可以總是在應用二分查找之前先對其進行排序。)的數據集合，查找思想有點類似于分治思想。每次都通過跟區間的中間元素對比，將帶查找的區間縮小為之前的一半，知道找到要查找的元素，或者區間被縮小為0。二分查找是一種非常非常高效的查詢算法，時間復雜度未O(logn)。

2.基本二分搜索

2.1基本二分搜索簡介與代碼模板

本分查找的最基礎和最基本的形式。
查找條件可以在不與元素的兩側進行比較的情況下確定（或使用它周圍的特定元素）。
不需要后處理，因為每一步中，你都在檢查是否找到了元素。如果到達末尾，則知道未找到該元素。

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 = left + (right - left) / 2;if(nums[mid] == target)return mid; else if(nums[mid] < target) left = mid + 1;elseright = mid - 1; }return -1; }

可能在基本二分搜索會遇到如下問題：

2.為什么 while 循環的條件中是 <=，而不是 <？

答：因為初始化 right 的賦值是 nums.length - 1，即最后一個元素的索引，而不是 nums.length。
這二者可能出現在不同功能的二分查找中，區別是：前者相當于兩端都閉區間 [left, right]，后者相當于左閉右開區間 [left, right)，因為索引大小為 nums.length 是越界的。
我們這個算法中使用的是前者 [left, right] 兩端都閉的區間。這個區間其實就是每次進行搜索的區間。
什么時候應該停止搜索呢？當然，找到了目標值的時候可以終止：

if(nums[mid] == target)return mid;

但如果沒找到，就需要 while 循環終止，然后返回 -1。那 while 循環什么時候應該終止？搜索區間為空的時候應該終止，意味著你沒得找了，就等于沒找到嘛。
while(left <= right) 的終止條件是 left == right + 1，寫成區間的形式就是 [right + 1, right]，或者帶個具體的數字進去 [3, 2]，可見這時候區間為空，因為沒有數字既大于等于 3 又小于等于 2 的吧。所以這時候 while 循環終止是正確的，直接返回 -1 即可。
while(left < right) 的終止條件是 left == right，寫成區間的形式就是 [left, right]，或者帶個具體的數字進去 [2, 2]，這時候區間非空，還有一個數 2，但此時 while 循環終止了。也就是說這區間 [2, 2] 被漏掉了，索引 2 沒有被搜索，如果這時候直接返回 -1 就是錯誤的。

2.此算法有什么缺陷？

比如說給你有序數組 nums = [1,2,2,2,3]，target 為 2，此算法返回的索引是 2，沒錯。但是如果我想得到 target 的左側邊界，即索引 1，或者我想得到 target 的右側邊界，即索引 3，這樣的話此算法是無法處理的。
這樣的需求很常見，你也許會說，找到一個 target，然后向左或向右線性搜索不行嗎？可以，但是不好，因為這樣難以保證二分查找對數級的復雜度了。怎么說呢，比如一個數組
[1,2,3,4,5,5,5,5,5,1],讓你找出target==5的右側邊界，你一次二分可以把5找出來，但是，你需要比較五次線性搜索才能才能找到右側邊界，是不是就很難保證時間復雜度

2.2LeetCode 69.x的平方根

題目描述：
實現 int sqrt(int x) 函數。
計算并返回 x 的平方根，其中 x 是非負整數。
由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842…,
由于返回類型是整數，小數部分將被舍去。

雙百二分：

class Solution { public:int mySqrt(int x) {if(x==1||x==0)return x;int left=0;int right=x;int mid;int ans;while(left<=right){mid=left+(right-left)/2;if((long long)mid*mid<=x){ans=mid;left=mid+1;}elseright=mid-1;}return ans;} };

2.3LeetCode 374.猜數字大小

我們正在玩一個猜數字游戲。 游戲規則如下：
我從 1 到 n 選擇一個數字。 你需要猜我選擇了哪個數字。
每次你猜錯了，我會告訴你這個數字是大了還是小了。
你調用一個預先定義好的接口 guess(int num)，它會返回 3 個可能的結果（-1，1 或 0）：
-1 : 我的數字比較小
1 : 我的數字比較大
0 : 恭喜！你猜對了！
示例 :
輸入: n = 10, pick = 6
輸出: 6

雙百二分：

/** * Forward declaration of guess API.* @param num your guess* @return -1 if num is lower than the guess number* 1 if num is higher than the guess number* otherwise return 0* int guess(int num);*/ class Solution { public:int guessNumber(int n) {int left=0;int right=n;int mid;while(left<=right){mid=left+(right-left)/2;if(guess(mid)==1)left=mid+1;else if(guess(mid)==-1)right=mid-1;elsereturn mid;}return mid;} };

2.4LeetCode33.搜索旋轉排序數組

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。
你可以假設數組中不存在重復的元素。
你的算法時間復雜度必須是 O(log n) 級別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1

代碼實現：

class Solution { public:int search(vector<int>& nums, int target) {int n = (int)nums.size();if (!n) return -1;if (n == 1) return nums[0] == target ? 0 : -1;int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) return mid;if (nums[0] <= nums[mid]) {if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return -1;} };

3.尋找左側邊界的二分搜索

3.1尋找左側邊界的二分搜索簡介與代碼模板

int left_bound(int[] nums, int target) {if (nums.length == 0) return -1;int left = 0;int right = nums.length; // 注意while (left < right) { // 注意int mid = (left + right) / 2;if (nums[mid] == target) {right = mid;//注意} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid; // 注意}}return left; }

可能你會存在很多疑問對這段代碼，不急一個一個來看

1.為什么 while 中是 < 而不是 <=?

用相同的方法分析，因為 right = nums.length 而不是 nums.length - 1。因此每次循環的「搜索區間」是 [left, right) 左閉右開。
while(left < right) 終止的條件是 left == right，此時搜索區間 [left, left) 為空，所以可以正確終止。

PS：這里先要說一個搜索左右邊界和上面這個算法的一個區別，也是很多讀者問的：剛才的 right 不是 nums.length - 1 嗎，為啥這里非要寫成 nums.length 使得「搜索區間」變成左閉右開呢？

因為對于搜索左右側邊界的二分查找，這種寫法比較普遍，我就拿這種寫法舉例了，保證你以后遇到這類代碼可以理解。你非要用兩端都閉的寫法反而更簡單，我會在后面寫相關的代碼，把三種二分搜索都用一種兩端都閉的寫法統一起來，你耐心往后看就行了。

2.while里為什么沒有返回 -1 的操作？如果 nums 中不存在 target 這個值，怎么辦？

因為要一步一步來，先理解一下這個「左側邊界」有什么特殊含義：

對于這個數組，算法會返回 1。這個 1 的含義可以這樣解讀：nums 中小于 2 的元素有 1 個。比如對于有序數組 nums = [2,3,5,7], target = 1，算法會返回 0，含義是：nums 中小于 1 的元素有 0 個。
再比如說 nums = [2,3,5,7], target = 8，算法會返回 4，含義是：nums 中小于 8 的元素有 4 個。
綜上可以看出，函數的返回值（即 left 變量的值）取值區間是閉區間 [0, nums.length]，所以我們簡單添加兩行代碼就能在正確的時候 return -1：

if(left != nums.size() && nums[left] == target) return left;return -1;

3.為什么 left = mid + 1，right = mid ？和之前的算法不一樣？

這個很好解釋，因為我們的「搜索區間」是 [left, right) 左閉右開，所以當 nums[mid] 被檢測之后，下一步的搜索區間應該去掉 mid 分割成兩個區間，即 [left, mid) 或 [mid + 1, right)。其實也就是while(left<right)中不帶等于的原因。保證查找空間在每一步中至少有 2 個元素。

4、為什么該算法能夠搜索左側邊界？

關鍵在于對于 nums[mid] == target 這種情況的處理：

if (nums[mid] == target)right = mid;

5.能不能想辦法把 right 變成 nums.length - 1，也就是繼續使用兩邊都閉的「搜索區間」？這樣就可以和第一種二分搜索在某種程度上統一起來了。

答案是當然可以，只要你明白了「搜索區間」這個概念，就能有效避免漏掉元素，隨便你怎么改都行。下面我們嚴格根據邏輯來修改：因為你非要讓搜索區間兩端都閉，所以 right 應該初始化為 nums.length - 1，while 的終止條件應該是 left == right + 1，也就是其中應該用 <=，如下：

int left_bound(int[] nums, int target) {// 搜索區間為 [left, right]int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) // 搜索區間變為 [mid+1, right]left = mid + 1;else if (nums[mid] > target) {// 搜索區間變為 [left, mid-1]right = mid - 1;else if (nums[mid] == target) {// 收縮右側邊界right = mid - 1;} }

由于 while 的退出條件是 left == right + 1，所以當 target 比 nums 中所有元素都大時，會存在以下情況使得索引越界：

因此，最后返回結果的代碼應該檢查越界情況：

if (left >= nums.length || nums[left] != target)return -1; return left;

所以完整的改進后：

int left_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;// 搜索區間為 [left, right]while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {// 搜索區間變為 [mid+1, right]left = mid + 1;} else if (nums[mid] > target) {// 搜索區間變為 [left, mid-1]right = mid - 1;} else if (nums[mid] == target) {// 收縮右側邊界right = mid - 1;}}// 檢查出界情況if (left >= nums.length || nums[left] != target)return -1;return left; }

3.2LeetCode278. 第一個錯誤的版本

你是產品經理，目前正在帶領一個團隊開發新的產品。不幸的是，你的產品的最新版本沒有通過質量檢測。由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的。
假設你有 n 個版本 [1, 2, …, n]，你想找出導致之后所有版本出錯的第一個錯誤的版本。
你可以通過調用 bool isBadVersion(version) 接口來判斷版本號 version 是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。
示例:
給定 n = 5，并且 version = 4 是第一個錯誤的版本。
調用 isBadVersion(3) -> false
調用 isBadVersion(5) -> true
調用 isBadVersion(4) -> true
所以，4 是第一個錯誤的版本。

// The API isBadVersion is defined for you. // bool isBadVersion(int version);class Solution { public:int firstBadVersion(int n) {int left=1;int right=n;int mid;while(left<=right){mid=left+(right-left)/2;if(isBadVersion(mid)==true)right=mid-1;else if(isBadVersion(mid)==false)left=mid+1;elseright=mid-1; }if(isBadVersion(left)==true)return left;return -1;} };

3.3LeetCode 162. 尋找峰值

峰值元素是指其值大于左右相鄰值的元素。
給定一個輸入數組 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
數組可能包含多個峰值，在這種情況下，返回任何一個峰值所在位置即可。
你可以假設 nums[-1] = nums[n] = -∞。
示例 1:
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函數應該返回其索引 2。
示例 2:
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數可以返回索引 1，其峰值元素為 2；
或者返回索引 5， 其峰值元素為 6。
說明:
你的解法應該是 O(logN) 時間復雜度的。

首先要注意題目條件，在題目描述中出現了 nums[-1] = nums[n] = -∞，這就代表著 只要數組中存在一個元素比相鄰元素大，那么沿著它一定可以找到一個峰值

class Solution { public:int findPeakElement(vector<int>& nums) {int left=0;int right=nums.size()-1;int mid;while(left<right){mid=left+(right-left)/2;if(nums[mid]>nums[mid+1])right=mid;elseleft=mid+1;}return left;} };

3.4LeetCode 153. 尋找旋轉排序數組中的最小值

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
請找出其中最小的元素。
你可以假設數組中不存在重復元素。
示例 1:
輸入: [3,4,5,1,2]
輸出: 1
示例 2:
輸入: [4,5,6,7,0,1,2]
輸出: 0

class Solution { public:int findMin(vector<int>& nums) {int left = 0;int right = nums.size() - 1; /* 左閉右閉區間，如果用右開區間則不方便判斷右值 */ while (left < right) { /* 循環不變式，如果left == right，則循環結束 */int mid = left + (right - left) / 2; /* 地板除，mid更靠近left */if (nums[mid] > nums[right]) { /* 中值 > 右值，最小值在右半邊，收縮左邊界 */ left = mid + 1; /* 因為中值 > 右值，中值肯定不是最小值，左邊界可以跨過mid */ } else if (nums[mid] < nums[right]) { /* 明確中值 < 右值，最小值在左半邊，收縮右邊界 */ right = mid; /* 因為中值 < 右值，中值也可能是最小值，右邊界只能取到mid處 */ }}return nums[left]; /* 循環結束，left == right，最小值輸出nums[left]或nums[right]均可 */ } };

4.尋找右側邊界的二分查找

4.1尋找右側邊界的二分查找簡介

int right_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] == target) {// 這里改成收縮左側邊界即可left = mid + 1;}}// 這里改為檢查 right 越界的情況，見下圖if (right < 0 || nums[right] != target)return -1;return right; }

最后一段代碼當 target 比所有元素都小時，right 會被減到 -1，所以需要在最后防止越界

4.2 LeetCode34.在排序數組中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
你的算法時間復雜度必須是 O(log n) 級別。
如果數組中不存在目標值，返回 [-1, -1]。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]

代碼：

class Solution { public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> vec;int left=0;int right=nums.size()-1;int mid;while(left<=right){mid=left+(right-left)/2;if(nums[mid]==target)right=mid-1;else if(nums[mid]>target)right=mid-1;elseleft=mid+1;}if(left==nums.size()||nums[left]!=target)vec.push_back(-1);elsevec.push_back(left);left=0;right=nums.size()-1;while(left<=right){mid=left+(right-left)/2;if(nums[mid]==target)left=mid+1;else if(nums[mid]<target)left=mid+1;elseright=mid-1;}if(right<0||nums[right]!=target)vec.push_back(-1);elsevec.push_back(right);return vec;} };

總結

以上是生活随笔為你收集整理的二分查找(循序渐进由0到1掌握二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。