二分查找算法应用于有序序列,其核心思想是通过比较中间元素和目标元素,每次缩小一半的查找区间,从而实现快速搜索。具体步骤如下:
- 定义查找区间
- 取查找区间中间元素,与目标元素进行比较
- 若相同,则返回
- 若不同,缩小查找区间,直到区间中没有待查找元素
在实现二分查找算法时,需特别注意以下细节:left
、right
变量的初始化、终止条件以及查找区间的缩小。要确保查找过程中不漏掉任何元素,并保持前后区间性质的一致性。什么是保证区间性质的一致性呢?就是说你一开始定义的初始化的区间是闭区间,后面缩小的过程中就不能突然缩成半开半闭区间。
left
,right
变量对应当前查找区间的范围。
查找某个元素
以升序序列 vector<int> nums
为例,假设我们按以下方式初始化 left
和 right
:
int left = 0, right = nums.size() - 1;
这意味着初始查找区间为闭区间 [left, right]
。后续代码应基于此编写,例如:
while (left <= right)
{
int middle = left + (right - left) / 2; // 防止溢出
if (nums[middle] == target)
{
return middle;
}
else if (nums[middle] > target)
{
left = middle + 1;
}
else if (nums[middle] < target)
{
right = middle - 1;
}
}
return -1;
首先分析终止条件。在这里,由于是闭区间,left <= right
的条件对应的终止情况是 left == right + 1
,此时查找区间为 [right + 1, right]
,即空区间,说明所有元素都被查找完了。否则,如果是left < right
,终止情况就会是left == right
,对应的查找区间是[right, right]
,这时候查找区间里还剩下一个元素,但是查找却终止了,也就是说我们查找的时候漏了这个元素,因此这个终止条件是错误的。
接着分析缩小查找区间范围的代码。相等的情况直接返回即可,不相等的情况需要排除 middle
元素,即从 middle
旁边的元素开始缩小查找区间,否则就会破坏了区间一致性,缩小出来的区间就不再是闭区间了。
同理,如果定义左闭右开区间,代码如下:
int left = 0, right = nums.size();
while (left < right)
{
int middle = left + (right - left) / 2;
if (nums[middle] == target)
{
return middle;
}
else if (nums[middle] > target)
{
left = middle + 1;
}
else if (nums[middle] < target)
{
right = middle;
}
}
return -1;
查找某个边界
例如,我们要查找比 target
小的元素个数或者说第一个不小于 target
的元素位置(有些地方也叫做左侧边界)。
首先定义初始查找区间,这里仍使用闭区间:
int left = 0, right = nums.size() - 1;
然后设置终止条件:
while (left <= right)
接下来思考如何缩小区间以实现目标。不相等的情况与上文相同,但由于我们要查找不小于(也就是大于等于) target
的元素,因此应将相等的情况纳入 nums[middle] > target
的情况中:
{
int middle = left + (right - left) / 2;
if (nums[middle] >= target)
{
right = middle - 1;
}
else if (nums[middle] < target)
{
left = middle + 1;
}
}
最后考虑应该返回left
还是right
。结束时,根据终止条件和缩小区间的代码,可知此时应该满足left = right + 1
、nums[right + 1] >= target
、nums[left - 1] < target
,即nums[left] >= target
、nums[right] < target
。因此,这里应该返回left
。
最后考虑应返回 left
还是 right
。循环结束时,根据终止条件和缩小区间的代码,变量满足 left = right + 1
、nums[right + 1] >= target
和 nums[left - 1] < target
,即 nums[left] >= target
和 nums[right] < target
。因此,这里应返回 left
。
其他情况同理。