二分查找/二分答案

0.前言

二分算法（Binary Search），也叫折半查找，是一种在有序数据集合中高效查找目标值的算法。它通过不断将查找范围缩小一半，快速定位目标，时间复杂度为 O(logn)，远优于线性查找的 O(n)。

1.原理

假设有一个升序排列的数组arr和一个目标值target，二分查找的过程如下：

• 定义两个指针分别指向数组的起始位置和结束位置。

• 计算中间索引并比较该位置上的元素与目标值的关系。

• 如果相等，则返回当前索引；如果小于目标值，则调整左边界继续向右半部分查找；反之则调整右边界向左半部分查找。

• 当左右边界重合仍未找到目标值时，说明数据集中不存在此值。

2.代码模板

#include<bits/stdc++.h> using namespace std; //检查是否符合条件 bool check(int a){ return ; } int main(){ int n,k; cin>>n>>k; int a[100055]; for(int i=1;i<=n;i++){ cin>>a[i]; } int l=1,r=1e8; while(l<r){ int m=(l+r)>>1; // 或m=(l+r)/2 if(check(m)){ l=m; }else{ r=m; } } cout<<l; }

3.时间复杂度

由于每次迭代都将问题规模减半，因此时间复杂度为 O(log n)