2025 8 3 XP02-1 晚笔记

二分查找

时间复杂度 O(logn)

前提: 数组是 有序的

1、二分模板
// 确定左右端点（二分范围）
int l = 左端点,r = 右端点;
int ans = 初始化;
while(l<=r){
// 1、找中间值
int mid=(l+r)/2;
// 2、比较查找到中间元素和目标元素的大小
if( ){ // 符合条件的情况
ans=mid; // 答案更新为 mid
// 缩小范围 画图！判断缩小左边界还是右边界
// l=mid+1; r=mid-1;
}
else{
// 缩小范围 和上一个反过来
// r=mid-1; l=mid+1;
}
}

3、lower_bound 和 upper_bound

在 a 数组中找到第一个大于等于 x 的元素 (下界)
lower_bound(a + 1, a + n + 1, x) - a;

在 a 数组中找到第一个大于 x 的元素 (上界)
upper_bound(a + 1, a + n + 1, x) - a; 

应用: 快速找到某个数 x 在 有序 数组中的个数
x 的下界 - x 的上界 = x 的个数