二分查找的概念

文章目录

二分查找的原理
二分查找的适用场景
二分查找的代码实现
目录

二分查找的原理

如果需要在 $n$ 个数中查找目标值是否存在，最常规的思想是遍历所有的数，判断每个数是否等于目标值。遍历的时间复杂度是 $O (n)$ 。

如果 $n$ 个数是有序的，则可以使用更低的时间复杂度查找目标值是否存在。假设 $n$ 个数按照升序排序，对于这 $n$ 个数中的一个数字 $x$ ，将其与目标值比较，可能有以下三种情况：

如果 $x$ 等于目标值，则找到目标值，因此目标值存在；
如果 $x$ 大于目标值，则所有大于等于 $x$ 的数都不可能是目标值，因此应该在小于 $x$ 的数中查找目标值；
如果 $x$ 小于目标值，则所有小于等于 $x$ 的数都不可能是目标值，因此应该在大于 $x$ 的数中查找目标值。

根据上述思想，如果每次查找时选取的 $x$ 是目标值可能存在的范围内的中间值，则经过一次查找可以将目标值可能存在的范围缩小一半。查找的次数是 $O(\log n)$ ，每次查找的时间是 $O (1)$ ，因此时间复杂度是 $O(\log n)$ ，显著低于遍历的时间复杂度 $O (n)$ 。

上述在有序数字中查找目标值的方法称为二分查找，也称折半查找。

以下用一个例子说明二分查找的过程。

给定长度为 $10$ 的数组： $[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]$ ，目标值是 $4$ 。

用 $\textit{low}$ 和 $\textit{high}$ 分别表示目标值可能存在的范围的下界和上界，初始时目标值可能存在的范围是整个数组， $\textit{low} = 0$ ， $\textit{high} = 9$ 。每次查找时，取 $\textit{mid}$ 为 $\textit{low}$ 和 $\textit{high}$ 的平均数向下取整，判断下标 $\textit{mid}$ 处的数和目标值的大小关系，调整查找范围。

根据 $\textit{low} = 0$ 和 $\textit{high} = 9$ 计算得到 $\textit{mid} = 4$ ，下标 $4$ 处的元素是 $8$ ，大于目标值 $4$ ，因此目标值一定在下标 $\textit{mid}$ 的左侧，将 $\textit{high}$ 更新为 $\textit{mid} - 1$ ，更新后 $\textit{high} = 3$ 。
根据 $\textit{low} = 0$ 和 $\textit{high} = 3$ 计算得到 $\textit{mid} = 1$ ，下标 $1$ 处的元素是 $2$ ，小于目标值 $4$ ，因此目标值一定在下标 $\textit{mid}$ 的右侧，将 $\textit{low}$ 更新为 $\textit{mid} + 1$ ，更新后 $\textit{low} = 2$ 。
根据 $\textit{low} = 2$ 和 $\textit{high} = 3$ 计算得到 $\textit{mid} = 2$ ，下标 $2$ 处的元素是 $4$ ，等于目标值 $4$ ，因此找到目标值，位于下标 $2$ 。

如果目标值是 $5$ ，则查找过程如下。

根据 $\textit{low} = 0$ 和 $\textit{high} = 9$ 计算得到 $\textit{mid} = 4$ ，下标 $4$ 处的元素是 $8$ ，大于目标值 $5$ ，因此目标值一定在下标 $\textit{mid}$ 的左侧，将 $\textit{high}$ 更新为 $\textit{mid} - 1$ ，更新后 $\textit{high} = 3$ 。
根据 $\textit{low} = 0$ 和 $\textit{high} = 3$ 计算得到 $\textit{mid} = 1$ ，下标 $1$ 处的元素是 $2$ ，小于目标值 $5$ ，因此目标值一定在下标 $\textit{mid}$ 的右侧，将 $\textit{low}$ 更新为 $\textit{mid} + 1$ ，更新后 $\textit{low} = 2$ 。
根据 $\textit{low} = 2$ 和 $\textit{high} = 3$ 计算得到 $\textit{mid} = 2$ ，下标 $2$ 处的元素是 $4$ ，小于目标值 $5$ ，因此目标值一定在下标 $\textit{mid}$ 的右侧，将 $\textit{low}$ 更新为 $\textit{mid} + 1$ ，更新后 $\textit{low} = 3$ 。
根据 $\textit{low} = 3$ 和 $\textit{high} = 3$ 计算得到 $\textit{mid} = 3$ ，下标 $3$ 处的元素是 $6$ ，大于目标值 $5$ ，因此目标值一定在下标 $\textit{mid}$ 的左侧，将 $\textit{high}$ 更新为 $\textit{mid} - 1$ ，更新后 $\textit{high} = 2$ 。此时 $\textit{low} > \textit{high}$ ，因此目标值不存在。

二分查找的适用场景

由于二分查找的原理是根据当前查找的数与目标值的大小关系缩小查找的范围，因此可以使用二分查找的前提条件是单调性。如果不具备单调性，则无法通过二分查找得到正确的结果。

二分查找有两个常见的适用场景：一是查找目标值是否存在；二是在特定范围中查找符合要求的最大值或最小值，称为二分查找判定问题。

对于第一个场景，常见的是在有序数组中查找目标值，变体包括将有序数组旋转之后查找目标值或最大/最小值。

对于第二个场景，需要利用单调性找到最值。假设符合要求的最值是 $x$ 。当 $x$ 是符合要求的最大值时，小于等于 $x$ 的值都符合要求，大于 $x$ 的值都不符合要求；当 $x$ 是符合要求的最小值时，大于等于 $x$ 的值都符合要求，小于 $x$ 的值都不符合要求。

二分查找的代码实现

二分查找的模板有很多。此处提供三种实现，适用于不同的场景。

第一种实现为最简单的二分查找实现，在给定的数组中查找目标值所在下标，当目标值不存在时返回 $- 1$ 。如果数组中有多个元素等于目标值，则返回其中一个元素所在下标。

class Solution {public int binarySearch(int[] nums, int target) {int low = 0, high = nums.length - 1;while (low <= high) {int mid = low + (high - low) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return -1;}
}

第二种实现为在给定的数组中查找大于等于目标值的最小元素所在下标，当数组中的所有元素都小于目标值时返回数组长度。

class Solution {public int binarySearch(int[] nums, int target) {int low = 0, high = nums.length;while (low < high) {int mid = low + (high - low) / 2;if (nums[mid] >= target) {high = mid;} else {low = mid + 1;}}return low;}
}

第三种实现为在给定的数组中查找小于等于目标值的最大元素所在下标，当数组中的所有元素都大于目标值时返回 $- 1$ 。

class Solution {public int binarySearch(int[] nums, int target) {int low = -1, high = nums.length - 1;while (low < high) {int mid = low + (high - low + 1) / 2;if (nums[mid] <= target) {low = mid;} else {high = mid - 1;}}return low;}
}

关于上述三种实现的说明如下。

上述三种实现为数组的场景，也可以推广到非数组的场景。后两种实现在二分查找判定问题中经常使用。
上述三种实现中，前两种实现的 $\textit{mid}$ 的计算等价于 $\textit{mid} = \Big\lfloor \dfrac{\textit{low} + \textit{high}}{2} \Big\rfloor$ ，第三种实现的 $\textit{mid}$ 的计算等价于 $\textit{mid} = \Big\lceil \dfrac{\textit{low} + \textit{high}}{2} \Big\rceil$ ，代码中的写法是为了避免溢出。
对于二分查找的实现，应注意每次查找之后都必须缩小查找范围，避免出现死循环。