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

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

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

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

leftright变量对应当前查找区间的范围。

查找某个元素

以升序序列 vector<int> nums 为例,假设我们按以下方式初始化 leftright

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 + 1nums[right + 1] >= targetnums[left - 1] < target,即nums[left] >= targetnums[right] < target。因此,这里应该返回left

最后考虑应返回 left 还是 right。循环结束时,根据终止条件和缩小区间的代码,变量满足 left = right + 1nums[right + 1] >= targetnums[left - 1] < target,即 nums[left] >= targetnums[right] < target。因此,这里应返回 left

其他情况同理。

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇