三分钟带你读懂什么是：二分查找算法

我们先来了解其定义：二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。

具体的搜索过程为：

从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。

前面的描述用伪代码表示如下：

""" 二分查找算法伪代码（Python 版本）: # 输入：nums 是有序数组，target 为要找的特定元素； # 输出：target 在 nums 中的索引位置，如果找不到则返回 -1； """ def binary_search(nums, target): st = left_bound(nums) # st 表示当前搜索区间的左边界 ed = right_bound(nums) # ed 表示当前搜索区间的右边界 while check(st, ed): mid = middle(st, ed) # 根据左右边界计算中间索引位置 if nums[mid] == target: return mid # 找到特定元素，返回索引位置 else if target < nums[mid]: ed = left(mid) # 在小于中间元素的那一半区间中查找 else if target > nums[mid]: st = right(mid) # 在大于中间元素的那一半区间中查找 return -1 # -1 代表没有在 nums 中找到 target

上面的伪代码中有几个点需要注意，这些地方也是二分查找算法容易出错的细节：

1. 主循环的停止判断条件 check(st, ed)

需要区分 st < ed 还是 st <= ed，这和开区间或是闭区间的选择有关；

2. 中间索引位置的计算公式 middle(st, ed)

当搜索区间的长度是偶数时，需要考虑到 mid 值是中间偏左还是偏右；

3. 二分搜索区间的更新公式 left(mid) 和 right(mid)

搜索区间的更新和开区间或是闭区间的选择有关。