题目描述

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

输入格式

第一行，一个整数 n，代表数组元素个数 ( n <= ${10}^6$ )

第二行，n 个数，代表数组的 n 个递增元素 ( 1 <= 数组元素值 <= ${10}^8$ )

第三行，一个整数 x ，代表要查找的数（ 0 <= x <= ${10}^8$）

输出格式

x 在数组中的位置，或者 -1 。

样例

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

2

程序填空

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,x;
int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&x);

	int mid,low,high;
	low = 1;
	high = n;
	while(low<= 填空(1) ) // [low,high]起码包含一个数字
	{
        if(填空(2)>x || 填空(3)<x ) //如果 x 比区域内最大的数大，或者比区域内最小的数小，那不可能找得到
            break;

		mid = (low+high)/2; // mid 是 区域的中间位置
		if(a[mid]==x) //找到
		{
			printf("%d",mid);
			return 0;
		}
		else if(a[mid]<x) //中间位置的数比 x 小，意味着 x 只可能在后半区
			low = 填空(4);
		else
			high = 填空(5); //中间位置的数比 x 大，意味着 x 只可能在前半区
	}

	// 跳出循环的，就是意味着找不到
	printf("-1");

	return 0;
}

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

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

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

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

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