题设：设数组a[0],…,a[n-1]中存放着n>=1个已由小到大排序的不同整数，判断整数x是否在数组a中。若是，返回j，使得x=a[j];否则，返回-1。
题解：利用数组中的整数已排序的性质，可以设计高效的求解算法。令left和right分别表示当前需要查找的数组部分的起点与终点下标。
初始时，left=0,right=n-1.令middle=[(left+right)/2]为中点下标。比较a[middle]和x，有如下三种可能：
①x<a[middle] 这时，若x存在，则x的下标一定在left~middle-1之间，因此，将right设置成middle-1.
②x==a[middle] 这时，返回middle 即可。
③x>a[middle] 这时，若x存在，则x的下标一定在middle+1~right之间，因此将left设置成middle+1.
如果x还未找到且数组a中还有可供查找的整数，则可以通过循环重新计算middle，继续查找。该算法包含两个子任务：
①判断是否还有可供查找的整数，这可转化为判断是否left<=right
②比较x和a[middle]，为了清晰描述整体算法，可用下面给出的compare函数实现。
1 char compare(int x,int y) 2 { 3 if (x>y) return '>'; 4 else if (x<y) return '<'; 5 else return '='; 6 }
得到二分查找函数
1 int BinarySearch(int *a,const int x,const int n) 2 { 3 for(int left=0,int right =n-1;left<=right;) 4 { 5 int middle=(left+right)/2; 6 switch(conpare(x,a[middle])) 7 { 8 case '>' :left=middle+1; break; 9 } 10 } 11 }
当left+right 为奇数时，每经过一次循环比较，新的查找范围为原来一半或一半-1；
当left+right 为偶数时，每经过一次循环比较，新的查找范围为原来的一半-1；