广告公司网站模版百度推广登录手机版

P2249 【深基13.例1】查找 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

①二分查找

②stl函数：lower_bound(a.begin(),a.end(),x) 返回第一个大于等于 x的数的地址

代码：

#include<iostream>
#include<algorithm>
using namespace std;int n, m;
int a[1000005];//int find(int x) //二分查找 
//{
//	int l = 1, r = n;
//	while (l < r)
//	{
//		int mid = l + (r - l) / 2;
//		if (a[mid] >= x) r = mid;
//		else l = mid + 1;
//	}
//
//	if (a[l] == x) return l; //找都了就输出他的位置 
//	else return -1; // 没找到输出-1 
//}
//
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];//待查询}while (m--){int x;cin >> x;int ans = lower_bound(a + 1, a + n + 1, x) - a;//可换二分查找if (x == a[ans])//找到了{cout << ans << " ";}elsecout << -1 << " ";}return 0;
}

总结：记二分查找代码和lower_bound用法