当前位置: 首页 > news >正文

二分查找算法详讲(三种版本写法)原创

介绍:

二分查找算法(Binary Search)是一种在有序数组中查找目标元素的算法。
它的基本思想是通过将目标元素与数组的中间元素进行比较,从而将搜索范围缩小一半。

  • 如果目标元素等于中间元素,则搜索结束;
  • 如果目标元素小于中间元素,则继续在左半部分查找;
  • 如果目标元素大于中间元素,则在右半部分查找。

通过不断地将搜索范围缩小一半,最终可以找到目标元素或确定目标元素不存在。

接下来通过例题介绍二分的不同写法

例题:

输入一个整数 n, 接下来一行输入 n 个整数(保证整数序列有序), 最后输入一个整数 m, 查找 m 在序列中的起始下标和结束下标

示例1:

输入:

5
1 2 2 4 5
2

输出:

1 2

解释:

2 在序列中的起始和结束位置是下标 1 和 2

代码讲解:

二分代码按照退出条件分为

  1. while (l <= r)
  2. while (l < r)

代码中的所有 lr 都是序列的左右闭区间

代码中的所有 l + r >> 1l + r + 1 >> 1 分别相当于 (l + r) / 2(l + r + 1) / 2>>是按位右移, 整数向右位移一位相当于除2

代码中的所有 x, 都是目标值, 也就是要查找的值; 所有的 idx, 是答案, 也就是要查找数的起始下标或结束下标

先讲第一种: while (l <= r), 在l > r时退出

// 查找起始下标
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;  // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1;  // 如果当前中间值比 x 小, 需要去序列的右区间, 因为mid位置的数比 x 小, 那么左边的区间(l, mid]的所有数都比 x 小else if (a[mid] > x) r = mid - 1;  // 同上else if (a[mid] == x)  // 等于答案时{idx = mid;r = mid - 1;  // 我们要找的时起始的下标, 虽然此时a[mid] == x, 但是mid的左边可能还有等于x的值, 所以我们要继续往左区间去找}
}// 查找结束下标(代码中只有注释的地方和上面的代码不一样)
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;  // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1;  else if (a[mid] > x) r = mid - 1;  else if (a[mid] == x)  {idx = mid;l = mid + 1;  // 我们要找的时结束的下标, 虽然此时a[mid] == x, 但是mid的右边可能还有等于x的值, 所以我们要继续往右区间去找}
}

观察上面代码我们可以把a[mid] == x的情况跟其他两种情况合并

// 查找起始下标
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;  // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] < x) l = mid + 1;  else if (a[mid] >= x){idx = mid;r = mid - 1;  // 继续往左区间找}
}// 查找结束下标
int l = 0, r = n - 1, idx = 0;
while (l <= r)
{int mid = l + r >> 1;if (a[mid] <= x){idx = mid;l = mid + 1;  // 继续往右区间找}else if (a[mid] > x) r = mid - 1;
}

下面讲第二种: while (l < r) 在l == r时退出

大家可以发现这种写法不需要 idx 这个变量来记录最终查找的x的起始下标或结束下标了, 因为最后l就是对应的起始下标或结束下标。(r等于l, 所以用r也行)

查找起始下标
int l = 0, r = n - 1;
while (l < r)
{int mid = l + r >> 1;  // 区间分成了两个 [l, mid] 和 (mid, r]if (a[mid] < x) l = mid + 1;// 当a[mid] == x的时候, r一直往左, 所以当有多个相同的x的话, 会查找到第一个else if (a[mid] >= x) r = mid;  // 因为a[mid]可能 == x, 因为mid也可能满足条件, 所以区间变成[l, mid]
}查找结束下标
int l = 0, r = n - 1, idx = 0;
while (l < r)
{				int mid = l + r + 1 >> 1;  // 区间分成了两个 [l, mid) 和 [mid, r]if (a[mid] > x) r = mid - 1;// 当a[mid] == x的时候, l一直往右, 所以当有多个相同的x的话, 会查找到最后一个else if (a[mid] <= x) l = mid;  // 因为a[mid]可能 == x, 因为mid也可能满足条件, 所以区间变成[mid, r]
}

接下来讲一下第二种查找结束下标的时候 为什么是 mid = l + r + 1 >> 1,而不是 mid = l + r >> 1;
c++默认向0取整, 对于正整数你可以说是向下取整, 也就是 5 / 2 = 2,
当出现 l = r - 1 的时候, 此时 mid = (l + r) / 2 向下取整后等于 r - 1 , 如果此时进入了a[mid] <= x的分支, 那么 l = mid = r - 1, 这时会发现 l 没有发生变化, 那么就会一直陷入死循环

先更到这里, 后面再补充

觉得写的不错的话, 点个赞吧

http://www.lryc.cn/news/356566.html

相关文章:

  • Git钩子(Hooks)之commit之前自动执行脚本
  • nano机器人2:机械臂的视觉抓取
  • 技术速递|宣布 Java on Azure 开发工具支持 Java on Azure Container Apps
  • 随机森林算法实现分类
  • Ubuntu卸载软件
  • 网络工程师:网络可靠性技术
  • 科技引领未来:高速公路可视化
  • Golang发送POST请求并传递JSON数据
  • C++实现生产者消费者模型
  • 【Mac】MWeb Pro(好用的markdown编辑器) v4.5.9中文版安装教程
  • C++ | Leetcode C++题解之第118题杨辉三角
  • 3D透视图转的时候模型闪动怎么解决?---模大狮模型网
  • 如何创建一个vue项目?详细教程,如何创建第一个vue项目?
  • AWS迁移与传输之Migration Hub
  • 网络渗透思考
  • 2.8万字总结:金融核心系统数据库升级路径与场景实践
  • Linux:进程控制(二.详细讲解进程程序替换)
  • Elasticsearch8.13.4版本的Docker启动关闭HTTPS
  • linux 之dma_buf (8)- ION简化版本
  • ⌈ 传知代码 ⌋ 高速公路车辆速度检测软件
  • scrapy 整合 mitm
  • linux大文件切割
  • 图像分割模型LViT-- (Language meets Vision Transformer)
  • CANDela studio之CDDT与CDD
  • Java中的注解(Annotation)是什么?它们有什么用途?
  • 【CUDA】Nsight profile驱动的CUDA优化
  • 字符串的拼接
  • HIVE3.1.3+ZK+Kerberos+Ranger2.4.0高可用集群部署
  • Android ANR Trace日志阅读分析技巧
  • 前端Ajax、Axios和Fetch的用法和区别笔记