在算法题中经常会出现搜索的题目，如果使用暴力搜索在数据量较大时会超时，（如\(10^5\)数量级时\(O(n^2)\)就会超时，\(O(nlogn)\)则通常不会），因此常用二分搜索等进行优化。
虽然stl库中关于二分搜索的接口很好用，很适合区间二分搜索，但我们仍需掌握C++实现二分搜索，“虽然这是一个简单的算法，但它的细节却惊人的可怕。”
1. C++实现二分搜索
以 AcWing 789. 数的范围 为例:
题目描述:
给定一个按照升序排列的长度为n的整数数组，以及q个查询。对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。如果数组中不存在该元素，则返回-1 -1。(数据范围\(10^5\))
#include <iostream>
using namespace std;
const int N=1e5+5;
int n,m,q[N];
int main ()
{
cin>>n>>m;
for (int i=0;i<n;i++) scanf("%d",&q[i]);
while (m--)
{
int k;
scanf("%d",&k);
int l=-1, r=n;
while(l+1!=r)
{
int mid=l+r>>1;
if (q[mid]>=k) r=mid;
else l=mid;
}
if (q[r]!=k) printf("-1 -1\n");
else
{
printf("%d ",r);
int ll=-1,rr=n;
while (ll+1!=rr)
{
int mid=ll+rr>>1;
if (q[mid]<=k) ll=mid;
else rr=mid;
}
if (q[ll]!=k) printf("%d\n",r);
else printf("%d\n",ll);
}
}
return 0;
}
r和ll分别逼近k范围的第一个数和最后一个数，r不存在说明k在数组中不存在。
使用stl接口实现版本较C++实现版慢5ms，差别不大。
2. 使用STL函数实现二分搜索
#include <bits/stdc++.h>
using namespace std;
int main()
{
int num[5] = {3, 1, 2, 5, 4};
int key = 3;
//二分搜索要求数组必须是有序的
sort(num,num+5);
// 第一个小于key的数的下标
int a = lower_bound(num, num + 5, key) - num - 1;//利用减去起始位置指针的方式转换为int下标
// 第一个大于key的数的下标
int b = upper_bound(num, num + 5, key) - num;
cout << a << ' ' << b << endl;
//查找某个值是否存在
cout << binary_search(num, num+5, 6);
return 0;
}
输出:
1 3
0
注意:
- lower_bound和upper_bound返回的是迭代器(指针)
- lower_bound和upper_bound默认数组是升序的,若数组是降序排列必须用
lower_bound(num, num + 5, key, greater<int>());
- 若查找值不存在,lower_bound和upper_bound返回第一个插入查找值而不影响原序列顺序的位置
- 调用函数前数组必须有序，若数组顺序和函数顺序不符/无序，会返回出错（-1或n）
相关知识
使用std::sort实现降序排序
实现1:bool cmp()
bool cmp(int x,int y)
return x>y;
实现2:
sort(num,num+5,greater<int>());//降序
sort(num,num+5,less<int>());//升序