P2249 【深基13.例1】查找题解

【问题分析】
本题有n个数（n > 10^6）n很大， 查找m 个数(m≤10^5) ，数最大为（10^9）

方法一：用顺序查找的话时间复杂度为：O（n * m）会超时， 只能得部分分；

方法二：用桶排时间复杂度为O（n）+ O（m），但是因为数最大为（10^{9）空间复杂度为：O（10}9）；

方法三：用二分查找，时间复杂度为：O(m * log n)，空间复杂度为O（n）。
综合以上的时间复杂度和空间复杂度，我们选用方法三。

【设计程序】

方法一：

#include<bits/stdc++.h>
using namespace std;
int const N = 1e6 + 5;//数组要开大一点
int a[N];
int n, m;
int find(int x)//查找此数的位置
{
	for(int i = 1;i <= n; i++)
		if (a[i] == x)//第一次遇到x时返回位置
			return i;
	return -1;//如果没找到
}
int main()
{
	int x;
	scanf ("%d%d", &n, &m);
	for (int i = 1;i <= n; i++)
		scanf ("%d", a + i);//输入数列
	for (int i = 1;i <= m; i++)
	{
		scanf ("%d", &x);//输入要查找的数
		printf ("%d ", find(x));//输出位置
	}
	return 0;
}//据检测全部TLE

方法二：
肯定超空间，所以此处不写。

方法三：

#include<bits/stdc++.h>
using namespace std;
int const N = 1e6 + 5;//数组要开大一点
int a[N];
int n, m;
int find(int x)//查找此数的位置
{
	int l = 1, r = n;//左右位置
	while (l <= r)
	//注：此写法中l和r在未查找过的数上
	{
		int m = (l + r) >> 1;//找中间位置
		if (a[m] < x)	l = m + 1;//判断
		else	r = m - 1;
	}
	if (a[l] == x)//如果找到
		return l;
	return -1;//如果没找到
}
int main()
{
	int x;
	scanf ("%d%d", &n, &m);
	for (int i = 1;i <= n; i++)
		scanf ("%d", a + i);//输入数列
	for (int i = 1;i <= m; i++)
	{
		scanf ("%d", &x);//输入要查找的数
		printf ("%d ", find(x));//输出位置
	}
	return 0;
}

【代码调试】

1. 测试样例

2. 自测数据（边界值，特殊值，本题中为第一个，最后一个，有重复，找不到）

自测（本题测试样例中已有第一个，有重复，找不到，只需再加最后一个即可）：

输入：
11 4
1 3 3 3 5 7 9 11 13 15 17
1 3 6 17

输出：
1 2 -1 11