二分查找
限制条件（1）顺序储存（数组）（2）有序

怎么理解二分查找
搜索区间为【left,right】,每次都会缩小一半的搜索区间

基础的二分查找
left=第一个数据的位置
right=最后一个数的位置
mid = left+(right-left)/2   (防止数据溢出int)
考虑三种情况,分别舍弃哪一部分搜索区间
a[mid]==x  ：cout<<mid;
a[mid]>x   : 舍弃右边包含mid  right=mid-1;
a[mid]<x   : 舍弃左边包含mid  left=mid+1;
循环的条件：left<=right

进阶的二分查找
查找第一个x:
循环的条件 ：left<right
a[mid]==x  ：right=mid;舍弃右边不包含mid

查找最后x:
循环的条件 ：left<right
a[mid]==x  ：left=mid;舍弃左边不包含mid

作业： 第一题：

#include<cstdio>
#include<iostream>
using namespace std;
int ar [100000]={0};

int main()
{
	int n,x_n,x;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>ar [i];
	}
	cin>>x_n;
	for(int i=1;i<=x_n;i++){
		int h=1,t=n,mid;
		cin>>x;
		while(h<t){
			mid = h+(t-h)/2;
			if(ar[mid]==x)t=mid;
			else if(ar[mid]>x)t=mid-1;
			else if(ar[mid]<x)h=mid+1;
		}
		if(ar[h]==x)cout<<ar[h]<<endl;
		else if(ar[h]>x){
			if(h==1) cout<<ar[h]<<endl;
			else if(ar[h]-x>=x-ar[h-1]){
				cout<<ar[h-1]<<endl;
			}else cout<<ar[h]<<endl;
		}else{
			if(h==n) cout<<ar[h]<<endl;
			else if(ar[h+1]-x>=x-ar[h]){
				cout<<ar[h]<<endl;
			}else cout<<ar[h+1]<<endl;
		}
	}
	return 0;
}

第二题：

第三题：