题目描述

请在一个有序递增数组中（不存在相同元素），采用二分查找，找出值 x 的位置，如果 x 在数组中不存在，请输出 -1 ！

输入格式

第一行，一个整数 n ，代表数组元素个数 ( n <= 600000 )

第二行，n 个数，代表数组的 n 个递增元素 ( 1 <= 数组元素值 <= 2000000 )

第三行，一个整数 x ，代表要查找的数 ( 0 <= x <= 2000000 )

输出格式

按题意输出位置或者 -1 。

样例

10
1 3 5 7 9 11 13 15 17 19
3

2

完成程序

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],x;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&x);
	a[n+1] = 2000001;
	a[0] = -1;
	int L=填空(1), R=填空(2), mid; //左右指针初始化
	
	while(L+1<R)
	{
		mid = 填空(3);
		if(a[mid]==x)
		{
			cout<<填空(4);
			return 0;
		}
		else
		{
			if(a[mid] 填空(5) x)
				L = mid;
			else
				R = mid;
		}
	}
	cout<<-1;

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}