&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 等。