二分法
二分法又可以被稱為二分查找，它描述了在有序集合中搜索特定值的程序，廣義的二分查找是將問題的規模盡可能的縮小到原有的一半，
對于二分法的思想大家都能講出幾句，但我們仍然很難講其與實際應用完美的結合到一起，所以我們盡量匯總二分法的應用場景，和大家一起深入，共勉！
一、常見問題
給定一個由數字組成的有序陣列 nums，并給你一個數字 target，問 nums 中是否存在 target，如果存在，則回傳其在 nums 中的索引，如果不存在，則回傳 - 1，
這是二分查找中最簡單的一種形式，當然二分查找也有很多的變形，這也是二分查找容易出錯，難以掌握的原因，
常見變體有：
- 如果存在多個滿足條件的元素，回傳最左邊滿足條件的索引，
- 如果存在多個滿足條件的元素，回傳最右邊滿足條件的索引，
- 陣列不是整體有序的， 比如先升序再降序，或者先降序再升序，
- 將一維陣列變成二維陣列…等等
二、二分查找中使用的術語
如前所述，二分查找是一種在每次比較之后將查找空間一分為二的演算法，每次需要查找集合中的索引或元素時，都應該考慮二分查找，如果集合是無序的，我們可以總是在應用二分查找之前先對其進行排序，但要注意排序的成本
target: 要查找的值index: 查找時的當前位置left和right: 左右指標mid: 左右指標的中點，用來確定我們應該向左查找還是向右查找的索引
在最簡單的形式中，二分查找對具有指定左索引和右索引的連續序列進行操作，這就是所謂的查找空間，二分查找維護查找空間的左、右和中間指示符，并比較查找目標或將查找條件應用于集合的中間值；如果條件不滿足或值不相等，則清除目標不可能存在的那一半，并在剩下的一半上繼續查找，直到成功為止，如果查以空的一半結束，則無法滿足條件，并且無法找到目標，
注意：
- 二分法搜索可以采用許多替代形式
- 可能并不總是直接搜索特定值
- 你不一定能直接縮小一半的查找范圍
- …
看過之后的幾個模版，并結合配套的例題，相信你會有自己的想法，
三、模版 I - 基礎二分查找
模版 I 是基礎的二分查找，用于查找可以通過訪問陣列中的單個索引來確定的元素或條件，
3.1 復雜度分析
- 平均時間復雜度：
O(logN) - 最壞時間復雜度：
O(logN) - 最優時間復雜度：
O(1)
3.2 關鍵點
- 二分查找的最基礎和最基本的形式，
- 查找條件可以在不與元素的兩側進行比較的情況下確定（或使用它周圍的特定元素），
- 不需要后處理，因為每一步中，你都在檢查是否找到了元素，如果到達末尾，則知道未找到該元素，
3.3 區分語法
- 初始條件：
left = 0right = arrar.length-1 或 number
- 終止：
left > right - 向左查找：
right = mid-1 - 向右查找：
left = mid+1
3.4 javascript 基礎模版
var search = function(nums, target) {
left = 0; // 初始左邊界
right = nums.length - 1; // 初始右邊界
while (left <= right) {
let mid = left + Math.floor((right - left) / 2); //防止溢位
if (nums[mid] < target) {
// 收縮左邊界
left = mid + 1;
} else if (nums[mid] > target) {
// 收縮右邊界
right = mid - 1;
} else {
return mid; // 找到了當前值
}
}
return -1;
};
3.5 代碼分析
- 確定初始的左右邊界:
left: 0right: nums.length-1mid: (left + (right - left) >> 1)
- 如果中間元素值
nums[mid]< target：證明中間值左側包括中間值都不符合要求，可以直接排除，left = mid + 1 - 如果中間元素值
nums[mid]：證明中間值右側包括中間值都不符合要求，可以直接排除，right = mid - 1 - 如果中間元素值
nums[mid]= target：直接回傳mid的下標 - 重新定義了左右邊界，也需要重新計算中間值，我們需要繼續進行范圍的排除
- 定義搜索的條件，應該是搜索區間都不為空，即
left <= right
3.6 LeetCode 實戰
下面五題，難度遞增，每篇題解都包含原題鏈接、模版分析、Js 題解，大家可以放心食用，我們一起加油～
- 二分查找（easy）
- 搜索插入的位置（easy）
- x 的平方根（easy）
- 猜數字大小（easy）
- 搜索旋轉排序陣列（middle）
四、模版 II - 依賴當前元素與右元素的關系
模板 II 是二分查找的高級模板，它用于查找需要訪問陣列中當前索引及其直接右鄰居索引的元素或條件，
4.1 關鍵點
- 查找條件需要訪問元素的直接右鄰居，
- 使用元素的右鄰居來確定是否滿足條件，并決定是向左還是向右，
- 保證查找空間在每一步中至少有 2 個元素，
- 需要進行后處理， 當你剩下 1 個元素時，回圈 / 遞回結束， 需要評估剩余元素是否符合條件，
4.2 區分語法
- 初始條件：left = 0, right = length
- 終止：left == right
- 向左查找：right = mid 這是因為向右判斷，一般需要保留比較元素，否則某些晴情況下會丟失資料
- 向右查找：left = mid+1
4.3 javascript 基礎模版
var search = function(nums, target) {
left = 0; // 初始左邊界
right = nums.length - 1; // 初始右邊界
while (left <= right) {
var mid = left + Math.floor(left + (right - left) / 2); //防止溢位
if (target == nums[mid]) {
right = mid + 1; // 繼續尋找左側是否仍存在滿足條件的元素，但包含當前元素
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (left != nums.length && nums[left] === target) return left;
return -1;
};
4.4 代碼分析
首先定義搜索區間為 [left, right]，注意是左右都閉合，之后會用到這個點，
- 終止搜索條件為 left <= right，
- 回圈體內，我們不斷計算 mid ，并將 nums[mid] 與 目標值比對，
- 如果 nums[mid] 等于目標值， 則收縮左邊界，注意它此時不代表最終結果
- 如果 nums[mid] 小于目標值， 說明目標值在 mid 右側，這個時候搜索區間可縮小為 [mid + 1, right]
- 如果 nums[mid] 大于目標值， 說明目標值在 mid 左側，這個時候搜索區間可縮小為 [left, mid - 1]
- 最后我們要判斷 left 值是否等于 target，如果不等于，證明沒找到
- 如果 left 出了右邊邊界了，說明也沒有找到
4.5 LeetCode 實戰
下面 3 題，難度遞增，每篇題解都包含原題鏈接、模版分析、Js 題解，大家可以放心食用，我們一起加油～
- 第一個錯誤的版本（easy）
- 尋找峰值（middle）
- 尋找旋轉排序陣列中的最小值（middle）
五、模板 III - 依賴當前元素與左右兩個元素之間的關系
模板 III 是二分查找的另一種獨特形式，它用于搜索需要訪問當前索引及其在陣列中的直接左右鄰居索引的元素或條件，
5.1 關鍵點
- 實作二分查找的另一種方法，
- 搜索條件需要訪問元素的直接左右鄰居，
- 使用元素的鄰居來確定它是向右還是向左，
- 保證查找空間在每個步驟中至少有 3 個元素，
- 需要進行后處理，當剩下
2個元素時，回圈 / 遞回結束，需要評估其余元素是否符合條件，
5.2 區分語法
- 初始條件：
left = 0, right = length - 1 - 終止：
left + 1 === right - 向左查找：
right = mid - 向右查找：
left = mid
5.3 javascript 基礎模版
function binarySearch(nums, target) {
const len = nums.length;
if (len === 0) return -1;
let left = 0;
let right = len - 1;
while (left + 1 < right) {
let mid = left + ((right - left) >> 1);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
5.4 代碼分析
因為我們的判斷區間最少為 2 個元素，所以我們要注意回圈的執行條件
- 簡單的判斷邊界：
nums.length === 0，return -1； - 定義初始的左右邊界：
left = 0, right = nums.length - 1； - 確定執行條件：
left + 1 < right，這也意味著查找區間要存在 3 個元素； - 向左查找時：
right = mid； - 向左查找時：
left = mid； - 判斷剩下的兩個元素哪個符合目標元素，并回傳結果；
5.5 LeetCode 實戰
下面 3 題，難度遞增，每篇題解都包含原題鏈接、模版分析、Js 題解，大家可以放心食用，我們一起加油～
- 在排序陣列中查找元素的第一個和最后一個位置（hard）
六、二分查找模板分析
本小結引自于LeetCode二分專題
上面提到的三個模版，大家在做題的時候很難完全套用進去，大部分時候，都是尋找最合適的方式并不斷調整
6.1 模版差異
這 3 個模板的不同之處在于：
- 左、中、右索引的分配，
- 回圈或遞回終止條件，
- 后處理的必要性，
個人感覺模版I最實用（其實是另外兩個模版掉頭發啊！）
6.2 模版示例
模板I (left <= right)
二分查找的最基礎和最基本的形式，
- 查找條件可以在不與元素的兩側進行比較的情況下確定（或使用它周圍的特定元素），
- 不需要后處理，因為每一步中，你都在檢查是否找到了元素，如果到達末尾，則知道未找到該元素，
模板II (left < right)
一種實作二分查找的高級方法，
- 查找條件需要訪問元素的直接右鄰居，
- 使用元素的右鄰居來確定是否滿足條件，并決定是向左還是向右，
- 保證查找空間在每一步中至少有 2 個元素，
- 需要進行后處理， 當你剩下 1 個元素時，回圈 / 遞回結束， 需要評估剩余元素是否符合條件，
模板III (left + 1 < right)
實作二分查找的另一種方法，
- 搜索條件需要訪問元素的直接左右鄰居，
- 使用元素的鄰居來確定它是向右還是向左，
- 保證查找空間在每個步驟中至少有 3 個元素，
- 需要進行后處理， 當剩下 2 個元素時，回圈 / 遞回結束， 需要評估其余元素是否符合條件，
七、其他經典問題
- pow(n, x)
- 有效的完全平方數
- 尋找比目標字母大的最小字母
- 統計有序矩陣中的負數
- 矩陣中戰斗力最弱的 K 行
八、寫在最后
本文解釋了三種最常見的解題模版，并附上LeetCode實戰，幫助我們理解二分法這種思想，
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- Github: Js 版 LeetCode 題解
- 前端進階筆記
- CSDN 博客匯總
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/242407.html
標籤：其他