1、算法思想:利用数据的有序性,通过二分排除,实现快速查找,时间复杂度O(logn)
2、适用条件:升序或降序序列
3、二分查找函数:lower_bound()、upper_bound()(假设数组a从小到大排序,下标从0开始,长度为n)
int p = lower_bound(a+0,a+n,k)-a :查找数组a中大于等于k的第1个位置p
int p = upper_bound(a+0,a+n,k)-a :查找数组a中大于k的第1个位置p
int p = lower_bound(s.begin(), s.end(), k)-s.begin():返回字符串s中大于等于k的第一个值的下标
int p = upper_bound(s.begin(), s.end(), k)-s.begin():返回字符串s中大于k的第一个值的下标
4、二分查找模板代码
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
while (m--) {
cin >> t;
int p = lower_bound(a + 0, a + n, t) - a;
if (p == n || a[p] != t) // 没找到t
cout << -1 << endl;
else
cout << p << endl;
}
return 0;
}