二分查找算法(Binary Search Algorithm):也叫做折半查找算法、对数查找算法,是一种用于在有序数组中查找特定元素的高效搜索算法。
二分查找的基本算法思想为:通过确定目标元素所在的区间范围,反复将查找范围减半,直到找到元素或找不到该元素为止。
以下是二分查找算法的基本步骤:
-
初始化:首先,确定要查找的有序数据集合。可以是一个数组或列表,确保其中的元素按照升序或者降序排列。
-
确定查找范围:将整个有序数组集合的查找范围确定为整个数组范围区间,即左边界
$left$ 和右边界$right$ 。 -
计算中间元素:根据
$mid = \lfloor (left + right) / 2 \rfloor$ 计算出中间元素下标位置$mid$ 。 -
比较中间元素:将目标元素
$target$ 与中间元素$nums[mid]$ 进行比较:- 如果
$target == nums[mid]$ ,说明找到$target$ ,因此返回中间元素的下标位置$mid$ 。 - 如果
$target < nums[mid]$ ,说明目标元素在左半部分($[left, mid - 1]$),更新右边界为中间元素的前一个位置,即$right = mid - 1$ 。 - 如果
$target > nums[mid]$ ,说明目标元素在右半部分($[mid + 1, right]$),更新左边界为中间元素的后一个位置,即$left = mid + 1$ 。
- 如果
-
重复步骤
$3 \sim 4$ ,直到找到目标元素时返回中间元素下标位置,或者查找范围缩小为空(左边界大于右边界),表示目标元素不存在,此时返回$-1$ 。
举个例子来说,以在有序数组
-
确定查找范围:初始时左边界
$left$ 为$0$ (数组的起始位置),$right$ 为$10$ (数组的末尾位置)。此时查找范围为$[0, 10]$ 。 -
计算中间元素:中间元素下标位置为
$5$ ,对应元素为$nums[5] == 5$ 。 -
比较中间元素:因为
$6 > nums[5]$ ,所以目标元素可能在右半部分,更新左边界为中间元素的后一个位置,即$left = 5$ 。此时查找范围为$[5, 10]$ 。 -
计算中间元素:中间元素下标位置为
$7$ ,对应元素为$nums[7] == 7$ 。 -
比较中间元素:因为
$6 < nums[7]$ ,所以目标元素可能在左半部分,更新右边界为中间元素的前一个位置,即$right = 6$ 。此时查找范围为$[5, 6]$ 。 -
计算中间元素:中间元素下标位置为
$5$ ,对应元素为$nums[5] == 5$ 。 -
比较中间元素:因为
$5 == nums[5]$ ,正好是我们正在查找的目标元素,此时返回中间元素的下标位置,算法结束。
于是我们发现,对于一个长度为
::: tabs#BinarySearch
@tab <1>
@tab <2>
@tab <3>
@tab <4>
@tab <5>
@tab <6>
@tab <7>
@tab <8>
:::
二分查找算法是经典的 「减而治之」 的思想。
这里的 「减」 是减少问题规模的意思,「治」 是解决问题的意思。「减」 和 「治」 结合起来的意思就是 「排除法解决问题」。即:每一次查找,排除掉一定不存在目标元素的区间,在剩下可能存在目标元素的区间中继续查找。
每一次通过一些条件判断,将待搜索的区间逐渐缩小,以达到「减少问题规模」的目的。而于问题的规模是有限的,经过有限次的查找,最终会查找到目标元素或者查找失败。
下面通过一个简单的例子来讲解下二分查找的思路和代码。
- 题目链接:704. 二分查找
描述:给定一个升序的数组
要求:返回
说明:
- 你可以假设
$nums$ 中的所有元素是不重复的。 -
$n$ 将在$[1, 10000]$ 之间。 -
$nums$ 的每个元素都将在$[-9999, 9999]$ 之间。
示例:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
- 设定左右边界为数组两端,即
$left = 0$ ,$right = len(nums) - 1$,代表待查找区间为$[left, right]$ (左闭右闭区间)。 - 取两个节点中心位置
$mid$ ,先比较中心位置值$nums[mid]$ 与目标值$target$ 的大小。- 如果
$target == nums[mid]$ ,则返回中心位置。 - 如果
$target > nums[mid]$ ,则将左节点设置为$mid + 1$ ,然后继续在右区间$[mid + 1, right]$ 搜索。 - 如果
$target < nums[mid]$ ,则将右节点设置为$mid - 1$ ,然后继续在左区间$[left, mid - 1]$ 搜索。
- 如果
- 如果左边界大于右边界,查找范围缩小为空,说明目标元素不存在,此时返回
$-1$ 。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
# 在区间 [left, right] 内查找 target
while left <= right:
# 取区间中间节点
mid = (left + right) // 2
# 如果找到目标值,则直接返回中心位置
if nums[mid] == target:
return mid
# 如果 nums[mid] 小于目标值,则在 [mid + 1, right] 中继续搜索
elif nums[mid] < target:
left = mid + 1
# 如果 nums[mid] 大于目标值,则在 [left, mid - 1] 中继续搜索
else:
right = mid - 1
# 未搜索到元素,返回 -1
return -1
- 时间复杂度:$O(\log n)$。
- 空间复杂度:$O(1)$。