教程长篇分享

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

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

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

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

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

查找某个元素

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

其他情况同理。


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

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

对这篇文章感觉如何?

太棒了
0
不错
0
爱死了
0
不太好
0
感觉很糟
0

You may also like

Leave a reply

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

More in:教程

教程

PuTTY 使用综合指南:SSH 连接 Linux

无论您是经验丰富的开发人员还是初学者,想在您的计算机和远程 Linux 服务器之间建立安全连接,PuTTY 是一个值得信赖的工具。让我们深入了解如何在 Windows 操作系统上利用 PuTTY 进行 […]
教程

在 Ubuntu 像22.04 LTS Linux 安装 JUnit 5

JUnit 不仅简单而且是一种有效的方法来编写和执行 Java 应用程序的单元测试,因此它是开源类别中使用最广泛的测试框架。 JUnit的最新版本5发布时带来了许多改进。 所以,如果你使用Ubuntu […]