刚学到二分,所以是手写二分的做法
查看原帖
刚学到二分,所以是手写二分的做法
1201753
fang_baby楼主2023/12/5 13:56

有一个坑点就是要要求输出这个数字在序列中第一次出现的编号,像我没学过bound函数的话就需要搜索首次出现的编号时继续用二分,不然最后一个会TLE

#include<cstdio>
using namespace std;

int main()
{
	int n, m, q, arr[1000005] = { 0 };
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	while (m--)
	{
		scanf("%d", &q);
		int left = 0, right = n - 1;
		while (left < right)
		{
			int c = (right - left) / 2 + left;
			if (arr[c] > q)
			{
				right = c;
			}
			else if (arr[c] < q)
			{
				left = c + 1;
			}
			else
			{
				left = c;
				right = c;
			}
		}

		if (arr[left] == q)
		{
			while (left != 0 && arr[left] == arr[left - 1])
			{
				right = left; left = 0;
				while (left < right)
				{
					int c = (right - left) / 2 + left;
					if (arr[c] > q)
					{
						right = c;
					}
					else if (arr[c] < q)
					{
						left = c + 1;
					}
					else
					{
						left = c;
						right = c;
					}
				}
			}
			printf("%d ", left + 1);
		}
		else
		{
			printf("-1 ");
		}
	}
	return 0;
}
2023/12/5 13:56
加载中...