二分查找一定要是有序的才可以查找，假如我要查找一个树x，给定的序列为1 2 3 4 5 6 7 8 9，那么我判断中间一个数，假如x大于中间那个数，就表明我要找的数在序列的右半部分，小于的话就在左半部分，然后在对半个序列进行同样的操作，所以也叫二分查找，时间复杂度降到O（log2 n）

下面的代码分递归与非递归两种

#include<iostream>
using namespace std;
int x,a[100];
int BinarySearch(int a[],int x,int left,int right)
{//递归
	 if(left<=right)
	 {
	 	int middle=(left+right)/2;
	 	if(x==a[middle])	return middle; 
	 	if(x<a[middle]) 	BinarySearch(a,x,left,middle-1);
		else	BinarySearch(a,x,middle+1,right);
	  }
	return -1;
}
int BinarySearch(int a[],int x,int n)
{//找到x时返回其在数组的位置，否则返回-1 
	int left=0,right=n-1;
	while(left<=right)
	{
		int middle=(left+right)/2;
		if(x==a[middle]) return middle;
		if(x<a[middle])	 right=middle-1;	
		else	left=middle+1;
	}
	return -1;//未找到x 
}
int main()
{
	int n;
	cin>>n;//n个数 
	for(int i=0;i<n;i++)	cin>>a[i];	
	cin>>x;//要找的数 
	cout<<BinarySearch(a,x,n)<<endl;
	return 0;	
}