優選算法系列（3.二分查找）

一.二分查找（easy）

題目鏈接：704. 二分查找 - 力扣（LeetCode）

解法：

代碼：

?二.在排序數組中查找元素的第?個和最后?個位置（medium）

題目鏈接：34. 在排序數組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）

解法：

代碼：

二分模板：

?三.搜索插入位置（easy）

題目鏈接：35. 搜索插入位置 - 力扣（LeetCode）

解法：

代碼：

?四.?x 的平方根（easy）

題目鏈接：69. x 的平方根 - 力扣（LeetCode）

解法：

代碼：

五：山峰數組的峰頂（easy）

題目鏈接：852. 山脈數組的峰頂索引 - 力扣（LeetCode）

解法：

代碼：

六：尋找峰值（medium）

題目鏈接：162. 尋找峰值 - 力扣（LeetCode）

解法：

代碼：

七：搜索旋轉排序數組中的最小值（medium）

題目鏈接：153. 尋找旋轉排序數組中的最小值 - 力扣（LeetCode）

解法：

代碼：

八：0?n-1 中缺失的數字（easy）

題目鏈接：LCR 173. 點名 - 力扣（LeetCode）

解法：

代碼：

一.二分查找（easy）

題目鏈接：704. 二分查找 - 力扣（LeetCode）

解法：

暴力解法無非就是從左到右枚舉，復雜度O（N）

但是這個數組是一個升序的，如果隨便取一個數比他小，那么所取得數左邊的數都比目標小這樣就只需要向他右邊找，如果比目標值大也一樣那么去它左邊找。

定義 left ， right 指針，分別指向數組的左右區間。
找到待查找區間的中間點 mid ，找到之后分三種情況討論：

arr[mid] == target 說明正好找到，返回 mid 的值；
arr[mid] > target 說明 [mid, right] 這段區間都是?于 target 的，因此舍去右邊區間，在左邊 [left, mid -1] 的區間繼續查找，即讓 right = mid - 1 ，然后重復 2 過程；
arr[mid] < target 說明 [left, mid] 這段區間的值都是?于 target 的，因此舍去左邊區間，在右邊 [mid + 1, right] 區間繼續查找，即讓 left = mid +1 ，然后重復 2 過程；

當 left 與 right 錯開時，說明整個區間都沒有這個數，返回 -1 。

代碼：

?二.在排序數組中查找元素的第?個和最后?個位置（medium）

題目鏈接：34. 在排序數組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）

解法：

暴力查找O（N）

?二分：

?的還是?分思想，就是根據數據的性質，在某種判斷條件下將區間?分為?，然后舍去其中?個區間，然后再另?個區間內查找；方便敘述，? x 表示該元素， resLeft 表示左邊界， resRight表示右邊界。

查找左端點

我們注意到以左邊界劃分的兩個區間的特點：

左邊區間 [left, resLeft - 1] 都是?于 x 的；
右邊區間（包括左邊界） [resLeft, right] 都是?于等于 x 的；

因此，關于 mid 的落點，我們可以分為下面兩種情況：

當我們的 mid 落在 [left, resLeft - 1] 區間的時候，也就是 arr[mid] < target 。說明 [left, mid] 都是可以舍去的，此時更新 left 到 mid + 1 的位置，繼續在 [mid + 1, right] 上尋找左邊界；
當 mid 落在 [resLeft， right] 的區間的時候，也就是 arr[mid] >= target 。說明 [mid + 1, right] （因為 mid 可能是最終結果，不能舍去）是可以舍去的，此時更新 right 到 mid 的位置，繼續在 [left, mid] 上尋找左邊界；

由此，就可以通過?分，來快速尋找左邊界；

注意：這?找中間元素需要向下取整。

因為后續移動左右指針的時候：

左指針： left = mid + 1 ，是會向后移動的，因此區間是會縮?的；
右指針： right = mid ，可能會原地踏步（?如：如果向上取整的話，如果剩下 1,2 兩個元素， left == 1 ， right == 2 ， mid == 2 。更新區間之后， left，right，mid 的值沒有改變，就會陷?死循環）。

因此?定要注意，當 right = mid 的時候，要向下取整。

循環條件：

?求中點操作：

?查找右端點

? resRight 表示右邊界；

我們注意到右邊界的特點：

左邊區間（包括右邊界） [left, resRight] 都是?于等于 x 的；
右邊區間 [resRight+ 1, right] 都是?于 x 的；

因此，關于 mid 的落點，我們可以分為下面兩種情況：

當我們的 mid 落在 [left, resRight] 區間的時候，說明 [left, mid - 1]（ mid 不可以舍去，因為有可能是最終結果）都是可以舍去的，此時更新 left 到 mid的位置；
當 mid 落在 [resRight+ 1, right] 的區間的時候，說明 [mid, right] 內的元素是可以舍去的，此時更新 right 到 mid - 1 的位置；

由此，就可以通過?分，來快速尋找右邊界；

注意：這?找中間元素需要向上取整。

因為后續移動左右指針的時候：

左指針： left = mid ，可能會原地踏步（?如：如果向下取整的話，如果剩下 1,2 兩個元素， left == 1， right == 2，mid == 1 。更新區間之后， left，right，mid 的值沒有改變，就會陷?死循環）。
右指針： right = mid - 1 ，是會向前移動的，因此區間是會縮小的；

因此?定要注意，當 right = mid 的時候，要向下取整。

代碼：

?C++：

java：

二分模板：

?三.搜索插入位置（easy）

題目鏈接：35. 搜索插入位置 - 力扣（LeetCode）

解法：

分析插入位置左右兩側區間上元素的特點：

[left, index - 1] 內的所有元素均是小于 target 的；
[index, right] 內的所有元素均是大于等于 target 的。

設 left 為本輪查詢的左邊界， right 為本輪查詢的右邊界。根據 mid 位置元素的信息，分析下?輪查詢的區間：

當 nums[mid] >= target 時，說明 mid 落在了 [index, right] 區間上，mid 左邊包括 mid 本?，可能是最終結果，所以我們接下來查找的區間在 [left,mid] 上。因此，更新 right 到 mid 位置，繼續查找。
當 nums[mid] < target 時，說明 mid 落在了 [left, index - 1] 區間上，mid 右邊但不包括 mid 本?，可能是最終結果，所以我們接下來查找的區間在 [mid+ 1, right] 上。因此，更新 left 到 mid + 1 的位置，繼續查找。