1WA 6TLE 问下二分判断左边界应该如何处理,疑似时间复杂度超了QWQ
查看原帖
1WA 6TLE 问下二分判断左边界应该如何处理,疑似时间复杂度超了QWQ
1313977
BUYA楼主2024/9/21 12:53
#include <stdio.h>
int erfen(int arr[], int low, int high,int target)
{
	int mid = (low + high) / 2;
	while (low <= high)
	{
		if (target > arr[mid])
		{
			low = mid + 1;
		}
		else if (target == arr[mid])
		{
			while (arr[mid - 1] == arr[mid])
			{
				mid -= 1;
			}
			return mid;
		}
		else if (target < arr[mid])
		{
			high = mid - 1;
		}
		mid = (low + high) / 2;
	}
	return -1;
}
int n, m,q;	int a = 0;	int arr[1000001];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &q);
		a=erfen(arr, 0, n, q);
		if (a >= 0)
		{
			a += 1;
		}
		printf("%d ", a);
	}
	return 0;
}
2024/9/21 12:53
加载中...