P2249 【深基13.例1】查找(第一篇博客)

【深基13.例1】查找 - 洛谷

思路：二分法

输入 n(nle10^6)n(n≤106) 个不超过 10^9109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a_1,a_2,dots,a_{n}a1​,a2​,…,an​，然后进行 m(mle10^5)m(m≤105) 次询问。对于每次询问，给出一个整数 q(qle10^9)q(q≤109)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。

第一行 2 个整数 n 和 m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

m 个整数表示答案。

输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出 #

1 2 -1 

代码如下:

#include 

using namespace std;

int n, m, c = 0;

int a[1000010];

int ans[100010];

int find(int l, int r, int k) {

	if (r - l == 1) {

		if (a[l] == k) return l;

		return -1;

	}

	else {

		int mid = l + (r - l) / 2;

			if (k <= a[mid - 1])find(l, mid, k);

			else find(mid, r, k);

	}

}

int main() {
	cin >> n >> m;

		for (int i = 1;  i <= n; i++) {


			cin>>a[i];

		}

	while (c < m) {

		c++;

		int k;

		cin >> k;

		ans[c] = find(1, n + 1, k);



	}

	for (int i = 1; i <= m; i++) {

		cout << ans[i] << " ";

	}

	return 0;

}

成功AC