&emsp;&emsp;二分查找（Binary Search）是對一種針對有序數據集合的查找算法，依賴數組，適合靜態數據。通過 n/2^k=1（k 是比較次數），可以求得 k=log2^n，因此時間復雜度為高效地 O(logn)。 &emsp;&emsp;其思路很簡單，就是每次與區間的中間數據做比較，縮小查找范圍，但是期間涉及到的細節很容易踩坑，例如比較時是否帶等號、mid值是否要加一等。例題：[704\. 二分查找](https://leetcode-cn.com/problems/binary-search/)。 &emsp;&emsp;LeetCode的[69\. x 的平方根](https://leetcode-cn.com/problems/sqrtx/)，x=sqrt(y); y=x^2，由于y和x是單調遞增的，因此可用二分查找，每次取中值，不斷逼近。另一種解題思路是牛頓迭代法。 &emsp;&emsp;在《劍指offer》一書中曾提到，寫出高質量的代碼需要了解3個方面： &emsp;&emsp;（1）規范性，書寫清晰、布局清晰和命名合理。 &emsp;&emsp;（2）完整性，完成基本功能、考慮邊界條件、做好錯誤處理。 &emsp;&emsp;（3）魯棒性，采取防御性編程、處理無效的輸入。 &emsp;&emsp;下面是二分查找最基本的代碼實現，改編自《[二分搜索](https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-fen-cha-zhao-xiang-jie)》，為了防止mid的溢出，才設計成了 low + Math.floor((high - low) / 2)。 ~~~ function binarySearch(nums, target) { let low = 0, high = ...; while(...) { let mid = low + ((high - low) >> 1); if (nums[mid] == target) { ... } else if (nums[mid] < target) { low = ... } else if (nums[mid] > target) { high = ... } } return ...; } ~~~ &emsp;&emsp;其中占位符“...”處就是容易出錯的細節部分： &emsp;&emsp;（1）循環退出條件。 &emsp;&emsp;（2）low 和 high 的更新。 &emsp;&emsp;（3）找到目標值時的處理。 &emsp;&emsp;（4）函數的返回值。 ## 一、無重復數據 &emsp;&emsp;在下面的[binarySearch()](https://codepen.io/strick/pen/mdVvWZx)函數中，nums是一個無重復數據的數組，需要注意： &emsp;&emsp;（1）while循環的判斷條件是小于等于，因為high的取值是末尾索引，相當于兩端閉區間 \[low, high\]。 &emsp;&emsp;（2）當不匹配時，縮小查找區間，分成兩塊閉區間：\[mid+1, high\] 或 \[low, mid-1\]。 ~~~ function binarySearch(nums, target) { let low = 0, high = nums.length - 1; //注意 while(low <= high) { //注意 let mid = low + ((high - low) >> 1); if (nums[mid] == target) { return mid; //注意 } else if (nums[mid] < target) { low = mid + 1; //注意 } else if (nums[mid] > target) { high = mid - 1; //注意 } } return -1; //注意 } ~~~ &emsp;&emsp;面試題11[旋轉數組的最小數字](https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/)。二分查找的思路，用兩個指針指向數組的第一個和最后一個元素，如果中間元素位于前面的遞增子數組，那么它應該大于或等于第一個指針指向的元素。 &emsp;&emsp;面試題53[在排序數組中查找數字](https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/)。用二分查找鎖定指定值，然后在左右兩邊順序掃描，直至找出第一個和最后一個指定值。延伸題：[0～n-1 中缺失的數字](https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/)。 ## 二、含重復數據 &emsp;&emsp;當查找的數組中包含重復數據時，二分查找需要做些處理。 &emsp;&emsp;面試題3[不修改數組找出重復數字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)。二分查找思想，從中間數字m分成兩部分，1~m和m+1~n，如果1~m的數字超過m，那么區間有重復數字。 **1）查找第一個等于給定值的元素** &emsp;&emsp;在下面的[binarySearchLow()](https://codepen.io/strick/pen/WNrPjdN)函數中，需要注意： &emsp;&emsp;（1）while循環的判斷條件是小于，因為 low 和 high 相等會陷入死循環。 &emsp;&emsp;（2）查找到匹配的數據不是立即返回，而是縮小范圍，并且增加一次 high 的邊界值判斷。 &emsp;&emsp;（3）在跳出循環后，需要最終判斷是否與目標值匹配。 ~~~ function binarySearchLow(nums, target) { let low = 0, high = nums.length - 1; while(low < high) { //注意 let mid = low + ((high - low) >> 1); if (nums[mid] == target) { high = mid - 1; //注意 if (nums[high] != target) //注意 return mid; //注意 } else if (nums[mid] < target) { low = mid + 1; } else if (nums[mid] > target) { high = mid - 1; } } return nums[low] == target ? low : -1; //注意 } ~~~ &emsp;&emsp;另一個類似的問題是查找最后一個等于給定值的元素，修改匹配時的范圍，如下所示。 ~~~ function binarySearchHigh(nums, target) { let low = 0, high = nums.length - 1; while(low < high) { let mid = low + ((high - low) >> 1); if (nums[mid] == target) { low = mid + 1; //注意 if (nums[low] != target) //注意 return mid; //注意 } else if (nums[mid] < target) { low = mid + 1; } else if (nums[mid] > target) { high = mid - 1; } } return nums[low] == target ? low : -1; } ~~~ **2）查找第一個大于等于給定值的元素** &emsp;&emsp;在下面的[binarySearchLow()](https://codepen.io/strick/pen/NWxogNr)函數中，需要注意： &emsp;&emsp;（1）修改匹配給定值的條件，變為大于等于。 &emsp;&emsp;（2）額外匹配一次 high 的邊界值，成功時直接返回 mid。 &emsp;&emsp;（3）修改跳出循環后的匹配條件。 ~~~ function binarySearchLow(nums, target) { let low = 0, high = nums.length - 1; while(low < high) { let mid = low + ((high - low) >> 1); if (nums[mid] >= target) { //注意 high = mid - 1; //注意 if (nums[high] < target) //注意 return mid; //注意 } else if (nums[mid] < target) { low = mid + 1; } } return nums[low] >= target ? low : -1; //注意 } ~~~ &emsp;&emsp;另一個類似的問題是查找最后一個小于等于給定值的元素，修改匹配時的范圍，如下所示。 ~~~ function binarySearchHigh(nums, target) { let low = 0, high = nums.length - 1; while(low < high) { let mid = low + ((high - low) >> 1); if (nums[mid] <= target) { //注意 low = mid + 1; //注意 if (nums[low] > target) //注意 return mid; //注意 } else if (nums[mid] > target) { high = mid - 1; } } return nums[low] <= target ? low : -1; //注意 } ~~~ &emsp;&emsp;本文的這些示例都沒有經過大量測試用例的嚴謹驗證，歡迎指正其中的潛在錯誤。 ***** > 原文出處： [博客園-數據結構和算法躬行記](https://www.cnblogs.com/strick/category/1809992.html) 已建立一個微信前端交流群，如要進群，請先加微信號freedom20180706或掃描下面的二維碼，請求中需注明“看云加群”，在通過請求后就會把你拉進來。還搜集整理了一套[面試資料](https://github.com/pwstrick/daily)，歡迎閱讀。  推薦一款前端監控腳本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不僅能監控前端的錯誤、通信、打印等行為，還能計算各類性能參數，包括 FMP、LCP、FP 等。