前言
二分查找是一种在有序数组中查找某一特定元素的搜索算法，在很多人的印象里，二分查找是一种比较简单的算法，然而在实际做题中，二分查找经常容易写错，特别是在处理边界条件的时候，今天我们就来聊一聊二分查找，看能不能找到一种比较简单，通用的方法来解决大部分的二分查找问题
先看一个例子
先给定一个数组
const list = [1, 2, 3, 5, 5, 5, 8, 9] 复制代码
思考下面4个问题
- 找到第一个 >=5 的元素
- 找到最后一个 <5 的元素
- 找到第一个 >5 的元素
- 找到最后一个 <=5 的元素
先简单想想来看下答案
以上其实就是我们在使用2分查找时经常会遇到的各种边界问题，而对于边界问题的处理，常常决定着最终结果的准确
如何分析问题
对于二分查找的问题，都可以抽象为在一个有序数组中寻找边界，以下以寻找蓝，红方块边界为例，最开始拿到数组是白色的，通过一次又一次的查找，去扩大蓝色 (左指针右移 left + 1) 和红色区域 (右指针左移 right - 1) ，最终找到边界 （即求出未知数K）
解题模板
大家来看一段伪代码
left = -1, right = n while left + 1 != right m = (left + right) / 2 if IsBlue(m) left = m else right = m return left or right 复制代码
做一道 leetCode 题
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
分析
二分查找都可以看做找边界 target 的问题，本题 left 左区域的值都小于 target (即蓝色区域) ，右边界的值都大于 target (即红色区域) ，而等于时即求出边界
解题
/** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { let left = -1 let right = nums.length while(left + 1 != right) { let middle = (left + right) >> 1 // 使用 >> 位运算代替除法避免小数 if (nums[middle] == target) { return middle } if (nums[middle] > target) { right = middle } if (nums[middle] < target) { left = middle } } return -1 }; 复制代码
怎么样，大家可以试试用这个解题模板去试试，看是否能让你做二分查找相关的题目时准确率更高些 ^-^
