找往期文章包括但不限于本期文章中不懂的知識點：

個人主頁：我要學編程(?_?)-CSDN博客

所屬專欄：?優(yōu)選算法專題

目錄

二分查找算法的介紹?

704. 二分查找

34. 在排序數(shù)組中查找元素的第一個和 最后一個位置

35. 搜索插入位置?

69. x的平方根?

總結

---

二分查找算法的介紹?

想必大家對這個算法應該不算陌生了，在C語言階段就已經(jīng)學習過了。?其是在暴力枚舉的基礎上進行優(yōu)化的。例如：在一個有序數(shù)組中查找某個元素是否存在。

但是二分查找算法也有缺點，就是需要數(shù)據(jù)有二段性，不一定是數(shù)組全部有序。

二分查找算法其實也是雙指針算法中對撞指針的一種拓展，主要是利用了數(shù)據(jù)的二段性。

下面我們就來進行練習。

704. 二分查找

題目：

給定一個?n?個元素有序的（升序）整型數(shù)組?nums?和一個目標值?target??，寫一個函數(shù)搜索?nums?中的?target，如果目標值存在返回下標，否則返回?-1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標為 4

示例?2:

輸入: nums = [-1,0,3,5,9,12], target = 2輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假設?nums?中的所有元素是不重復的。
2. n?將在?[1, 10000]之間。
3. nums?的每個元素都將在?[-9999, 9999]之間。

思路：這里既可以使用最簡單的暴力枚舉，也可以使用二分查找來解決。

代碼實現(xiàn)：

暴力枚舉：

class Solution {public int search(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {if (nums[i] == target) {return i;}}return -1;}
}

?二分查找：

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;while (left <= right) { // 這里得判斷=的情況int mid = (left+right) / 2; // 這里可能會有溢出的風險if (nums[mid] > target) {right = mid-1;} else if (nums[mid] < target) {left = mid+1;} else {return mid;}}return -1;}
}

注意：由于本題數(shù)據(jù)量不是很大，因此 mid = (left+right) / 2; 就不會溢出，但是當數(shù)據(jù)量非常大時，兩者相加就會導致溢出。有小伙伴可能會有疑惑：left 為 0，right 在 int 中，為什么會導致溢出呢？確實這種情況是正常的，但是當?shù)诙斡嬎鉳id 且left 為上一次的mid 值呢？這就會溢出了。解決辦法為：mid = left + (right -?left)/2；上面這個題目只是來練練手，下面才開始真正的算法題。

34. 在排序數(shù)組中查找元素的第一個和 最后一個位置

題目：

給你一個按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個目標值?target。請你找出給定目標值在數(shù)組中的開始位置和結束位置。

如果數(shù)組中不存在目標值?target，返回?[-1, -1]。

你必須設計并實現(xiàn)時間復雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例?2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109?<= nums[i]?<= 109
• nums?是一個非遞減數(shù)組
• -109?<= target?<= 109

思路：題目說給的數(shù)組是非遞減的，什么意思呢？

這里要查找的不是一個元素，而是一組連續(xù)的數(shù)據(jù)，也就是一段連續(xù)的子區(qū)間。 這里可能有小伙伴會想到我們前面學習的滑動窗口算法求子序列的問題。 但是這里不應該優(yōu)先使用這個方法，因為滑動窗口算法是同向雙指針， 而這里我們推測出了數(shù)據(jù)的特性，應該優(yōu)先使用二分查找。

這里是要查找一組數(shù)據(jù)的端點下標，那么我們就可以直接忽略這組數(shù)據(jù)的中間，直接找端點即可。那么這就從查找一段數(shù)據(jù)，變?yōu)榱瞬檎覂蓚€值。但是新的問題又來了，怎么找端點呢？相信有聰明的小伙伴已經(jīng)想到怎么做了。直接暴力枚舉去遍歷數(shù)組就完了。沒錯，這雖然是一個笨辦法，但是總好過沒有辦法。

遍歷的方式：從數(shù)組最左端開始遍歷，找左端點，接著從數(shù)組最右端開始，找右端點即可。

代碼實現(xiàn)：

class Solution {public int[] searchRange(int[] nums, int target) {int[] ans = {-1,-1};if (nums.length == 0) { // 排除特殊情況return ans;}// 找左端點int left = 0;while (left < nums.length && nums[left] != target) { // 防止越界left++;}if (left == nums.length) { // 數(shù)組中沒有目標值return ans;} else {ans[0] = left;}// 找右端點int right = nums.length-1;while (right >= 0 && nums[right] != target) { // 防止越界right--;}if (right >= 0) {ans[1] = right;}return ans;}
}

雖然這是暴力枚舉，但是從力扣上面的結果來看，還是不錯的。

上面的方法可以說是流氓做法了，不符合題目的要求：用二分查找來解決。

二分查找同樣還是去找符合數(shù)據(jù)的左端點和右端點。

尋找左端點過程：

尋找右端點過程（精簡版）：

上面處理這么多，其實就是在證明三件事：

1、根據(jù)查找的端點位置，從而劃分了合法區(qū)域和非法區(qū)域，因為端點位置肯定是在有效區(qū)域內的。再根據(jù) left 和 right 的相對位置來判斷下一步的走向。

左端點：left = mid + 1 ---> 跳出非法區(qū)域；right = mid ---> 保留在合法區(qū)域。

右端點：left = mid ---> 保留在合法區(qū)域；right = mid -1 ---> 跳出非法區(qū)域。

2、在查找的過程中，中點的選取。根據(jù)查找的端點位置和第一點的結論，從而決定中點的位置。

左端點：right = mid 的特性可能會導致最后死循環(huán)，因此中點盡量要靠左，即 mid = left + (right-left) / 2。

右端點：left = mid?的特性可能會導致最后死循環(huán)，因此中點盡量要靠右，即 mid = left + (right-left +1) / 2。

3、 查找左端點和右端點的過程中，循環(huán)條件只能是 left < right，絕不能出現(xiàn)等于的情況，可能會導致死循環(huán)。因為一旦相遇并且結果滿足 right 或者 left 不動的情況，那么就會死循環(huán)。

上面這些細節(jié)問題處理完之后，代碼就比較好寫了。

代碼實現(xiàn)：

class Solution {public int[] searchRange(int[] nums, int target) {int[] ans = {-1,-1};if (nums.length == 0) { // 排除特殊情況return ans;}// 找左端點int left = 0;int right = nums.length-1;while (left < right) {int mid = left + (right-left) / 2; // 找靠左的位置if (nums[mid] >= target) {right = mid; // 保證在合法區(qū)域內} else {left = mid+1; // 保證有可能跳出非法區(qū)域}}// 走到這里，說明left與right相遇了if (nums[left] == target) { // 判斷是否為左端點ans[0] = left; // left 與 right 都是可以的} else { // 說明數(shù)組中沒有要找的數(shù)據(jù)return ans;}// 找右端點left = 0;right = nums.length-1;while (left < right) {int mid = left + (right-left+1) / 2; // 找靠右的位置if (nums[mid] <= target) {left = mid; // 保證在合法區(qū)域內} else {right = mid-1; // 保證有可能跳出非法區(qū)域}}// 走到這里，說明left與right相遇了if (nums[right] == target) { // 判斷是否為右端點ans[1] = right; // left 與 right 都是可以的}return ans;}
}

還有兩個要注意的地方：

因此數(shù)組中一旦存在我們要查找的數(shù)據(jù)的話，肯定是存在左右端點的。

35. 搜索插入位置?

題目：

給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值，并返回其索引。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為?O(log n)?的算法。

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例?2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums?為?無重復元素?的?升序?排列數(shù)組
• -104 <= target <= 104

思路：這里和第一題有點類似，但不同的是這一題的數(shù)組中可能不存在 target 這個數(shù)據(jù)。但是方法還是類似的。

當 [target，right] 區(qū)間是合法區(qū)間時，right = mid ---> 保證 right 在合法區(qū)間內，left = mid+1 ---> 保證 left 有可能進入合法區(qū)間，mid = left + (right - left) / 2 ---> 靠左的位置。同理，當[left，target]為合法區(qū)間時，也是類似的，這里就不過多贅述了。

代碼實現(xiàn)：

1、當 [left, target] 是合法區(qū)間時：

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length-1;// 假設[left, target]是合法區(qū)間while (left < right) {int mid = left + (right-left+1) / 2;if (nums[mid] > target) {right = mid-1;} else {left = mid;}}// 判斷是否存在if (nums[left] == target) { // 實際存在return left;} else { // 不存在// 判斷是插入左邊還是右邊位置if (nums[left] > target) {return left;} else {return left+1;}}}
}

2、?當 [target，right] 是合法區(qū)間時：

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length-1;// 假設[target, right]是合法區(qū)間while (left < right) {int mid = left + (right-left) / 2;if (nums[mid] >= target) {right = mid;} else {left = mid+1;}}// 判斷是否存在if (nums[left] == target) { // 實際存在return left;} else { // 不存在// 判斷是插入左邊還是右邊位置if (nums[left] > target) {return left;} else {return left+1;}}}
}

69. x的平方根?

題目：

給你一個非負整數(shù)?x?，計算并返回?x?的?算術平方根?。

由于返回類型是整數(shù)，結果只保留?整數(shù)部分?，小數(shù)部分將被?舍去 。

注意：不允許使用任何內置指數(shù)函數(shù)和算符，例如?pow(x, 0.5)?或者?x ** 0.5?。

示例 1：

輸入：x = 4
輸出：2

示例 2：

輸入：x = 8
輸出：2
解釋：8 的算術平方根是 2.82842..., 由于返回類型是整數(shù)，小數(shù)部分將被舍去。

提示：

• 0 <= x <= 231 - 1

思路： 題目讓我們求一個大于等于0整數(shù)的算術平方根，并且對最終結果進行向下取整。

方法一：直接暴力枚舉即可。

代碼實現(xiàn)：

class Solution {// 暴力枚舉public int mySqrt(int x) {if (x == 0 || x == 1) { // 排除特殊情況return x;}for (long i = 1; i <= x; i++) {if (i * i == x) {return (int)i;} else if (i * i > x) {return (int)i-1;}}return -1; // 這里只是過審}
}

注意：由于最后面的 return -1；只是為了讓我們的代碼編譯通過，并不起實際的作用。

我們前面的暴力枚舉就是把 [1，x] 之間的數(shù)據(jù)按照升序的方式挨個使了個遍。?從這里我們就可以使用二分查找算法了。

其實我們最終的目的就是為了找到大于或者的結果，然后再讓大于的-1，等于的不變，而這些只能讓 target 和 left 在一起。

代碼實現(xiàn)：

class Solution {// 二分查找public int mySqrt(int x) {if (x == 0 || x == 1) { // 排除特殊情況return x;}long left = 1;long right = x;// 最終的結果是向下取整的，即 <= 是合法區(qū)域的while (left < right) {long mid = left + (right-left+1) / 2;if (mid*mid > x) {right = mid-1;} else {left = mid;}}// 找到了return (int)left;}
}

注意：

1、數(shù)據(jù)量是比較大的，因此相乘的結果會溢出，我們得用 long類型來接收。?

2、這里的二分查找是不能使用第一道題的那種的。

其實沒弄明白也沒關系，這里反正就兩種情況，可以直接去套用，再不濟暴力枚舉總可以了吧。

總結

1、對于查找固定的數(shù)據(jù)的情況，可以使用第一題中的二分查找方法：根據(jù)要查找的結果，進行比較分為三種情況——大于、等于、小于。

2、對于范圍(區(qū)間)查找和不確定性查找的情況，可以使用我們后面畫圖推出來的二分查找：根據(jù)查找的結果，進行比較分為兩種情況——合法區(qū)域、非法區(qū)域（根據(jù)要查找的數(shù)據(jù)進行分區(qū)），然后再分別更新 left 和 right——合法的一定要確保依舊存在于合法區(qū)域，非法的要確保有希望調到合法區(qū)域。再就是計算中點的方式和循環(huán)條件的確定，都是由 left 和 right 的變化來決定的（具體可見圖）。

我們以后常用的也是第二種二分查找的方法。

好啦！本期?二分查找算法專題（1）的學習之旅就到此結束啦！我們下一期再一起學習吧！