秦皇岛网站制作方案,wordpress推广码,小说网站建设之前需求分析,东莞网站设计哪家好二分查找详解与实现#xff1a;左闭右闭区间#xff08;二分模板 1#xff09;
个人比较习惯的二分模版
一、引言
二分查找#xff08;Binary Search#xff09;是一个高效的搜索算法#xff0c;它在有序数组中以对数时间复杂度 O(log n) 搜索目标元素的位置。二分查找…二分查找详解与实现左闭右闭区间二分模板 1
个人比较习惯的二分模版
一、引言
二分查找Binary Search是一个高效的搜索算法它在有序数组中以对数时间复杂度 O(log n) 搜索目标元素的位置。二分查找非常适合用在「值单调」的问题中如在一个升序数组中查找某个值是否存在、某个条件的最小值/最大值等。
本篇文章主要介绍一种最常用且稳定的二分查找模板左闭右闭区间 [left, right] 的实现方法。 二、适用前提
使用二分查找有以下几个前提条件
数组必须有序升序或降序均可支持随机访问如数组或 vector可比较目标值与当前值的大小关系 三、基本思想
在二分查找中我们反复将搜索区间划分为两半并根据目标值的位置来缩小搜索范围。
区间定义左闭右闭 [left, right]
包括 left 和 right 所指的元素即搜索区间为 a[left] ~ a[right]。因此当 left right 时区间仍然有效循环条件为 left right。 四、为什么这样写三点解释
---- int mid left (right - left) / 2 的原因
使用 (left right) / 2 有溢出风险尤其在 left 和 right 很大时可能导致整型溢出因此推荐使用
int mid left (right - left) / 2;或者位运算版本
int mid left ((right - left) 1);---- 为什么 while (left right)
因为我们采用的是左闭右闭区间 [left, right]在 left right 时 a[left] 依然是有效元素因此需要用 。
----为什么 right mid - 1 和 left mid 1
a[mid] target说明目标在左边 → 舍弃 mid 本身因为不等于目标 → right mid - 1a[mid] target目标在右边 → 舍弃 mid 本身 → left mid 1 五、完整代码实现含详尽注释
#include iostream
#include vector
using namespace std;int main()
{// 示例有序数组升序vectorint a { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };// 输入要查找的目标值int target;cout 请输入要查找的目标值: ;cin target;// 定义左闭右闭区间 [left, right]int left 0;int right a.size() - 1;// 二分查找过程while (left right){// 计算中间索引防止溢出的写法int mid left (right - left) / 2;// 如果找到了目标if (a[mid] target){cout 目标值 target 的索引是: mid endl;return 0;}// 如果中间值大于目标目标在左区间else if (a[mid] target){right mid - 1;}// 如果中间值小于目标目标在右区间else{left mid 1;}}// 若执行到此处说明未找到目标值cout 目标值 target 不存在于数组中 endl;cout -1 endl;return 0;
}六、常见错误总结
错误写法错误原因while (left right)会漏掉最后一个元素的判断。若目标值恰好是 a[right]会漏查mid (left right)/2有可能溢出区间定义不清晰容易导致死循环或漏查建议固定一种模板 七、模板通用性说明
左闭右闭区间的模板是最常用的写法它的好处是逻辑清晰循环条件为 left right比「左闭右开」更容易处理收敛边界情况。
