二分查找相关知识点
2025-02-08 16:55:41
发布于：上海
22阅读
0回复
0点赞
二分查找（又称折半查找）
基础二分查找作用：在有序序列中查找 或 的前驱/后继
*注意：一定要在有序序列中查找
先来讲述一下如何在有序序列中查找 或 的前驱/后继
一般需要一个左端点，一个右端点，一个中间值（作为下标，然后在这个区间内进行寻找）；每次查看中间值是否为的前驱/后继,然后改变左端点的值或右端点的值。
*改变左/右端点的值：比如说，在单调递增序列中寻找 的值
A8019.查找x: https://www.acgo.cn/problemset/info/8019
#include<bits/stdc++.h>//万能头
using namespace std;
int a[105];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];//输入
int x;
cin>>x;
int left=1;
int right=n;
//二分查找的左端点和右端点有很多种写法，这里是一种（比较简单且容易理解的）左闭右闭区间[]，也就是将数据范围分为三个部分
//[left,mid-1][mid][mid+1,right]
int ans=-1;
//ans(answer)记录答案，初始值按照题目要求改为-1
while(left<=right){
int mid=(left+right)/2;
if(a[mid]==x){
//如果找到要求值，记录下来，退出循环
ans=mid;
break;
}else if(a[mid]<x){
//[left,mid-1][mid][mid+1,(x,)right](发现x在第三个部分，将左端点转移到mid+1,在[mid+1,right]之间查找)
left=mid+1;
}else if(a[mid]>x){
right=mid-1;
//[left,(x,)mid-1][mid][mid+1,right](发现x在第一个部分，将右端点转移到mid-1,在[left,mid-1]之间查找)
}
}
cout<<ans;
}
一些其他的相关知识：
lower_bound:
lower_bound(a(数组名)+第一个下标,a+最后一个下标+1,x(查找目标))-a(建议先减a，不然返回的是地址）;
写出来就是：
lower_bound(a+1,a+1+n,x)
找到则返回第一个大于等于x的值的位置，找不到则返回最后一个下标+1
upper_bound:
upper_bound(a(数组名)+第一个下标,a+最后一个下标+1,x(查找目标))-a(建议先减a，不然返回的是地址）;
写出来就是：
upper_bound(a+1,a+1+n,x)
找到则返回第一个大于x的值的位置，找不到则返回最后一个下标+1
这里空空如也
有帮助，赞一个