掌握二分查找算法：初始化、查找区间与终止条件

二分查找算法应用于有序序列，其核心思想是通过比较中间元素和目标元素，每次缩小一半的查找区间，从而实现快速搜索。具体步骤如下：

1. 定义查找区间
2. 取查找区间中间元素，与目标元素进行比较
   1. 若相同，则返回
   2. 若不同，缩小查找区间，直到区间中没有待查找元素

在实现二分查找算法时，需特别注意以下细节：left、right 变量的初始化、终止条件以及查找区间的缩小。要确保查找过程中不漏掉任何元素，并保持前后区间性质的一致性。什么是保证区间性质的一致性呢？就是说你一开始定义的初始化的区间是闭区间，后面缩小的过程中就不能突然缩成半开半闭区间。

left，right变量对应当前查找区间的范围。

查找某个元素

以升序序列 vector 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 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[right] = target 和 nums[left - 1] = target 和 nums[right] < target。因此，这里应返回 left。

其他情况同理。

本文链接: https://linuxstory.org/mastering-binary-search-initialization-interval-termination

LinuxStory 原创教程，转载请注明出处，否则必究相关责任。