1.实践题目：输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
2.问题描述：即对含n个整数的序列进行二分查找，找到所要查找的数时则返回其下标，找不到则返回-1，同时返回查找次数。
3.算法描述：
1 int BinarySearch (int *a, int size, int key) 2 { 3 if(key < 0 || key > a[size-1]) return -1; 4 int left = 0; 5 int right = size - 1; 6 int t = 0; 7 8 while (left <= right ) 9 { 10 t++; 11 int mid = (left + right) / 2; 12 if (a[mid] == key ) 13 { 14 cout << mid << endl; 15 cout << t ; 16 return mid ; 17 } 18 if (key < a[mid] ) 19 right = mid - 1; 20 else left = mid + 1; 21 } 22 cout << "-1" <<endl; 23 cout << t << endl; 24 return -1; 25 }
首先对序列设置左边界和右边界，并且由左右边界定义中值，进入循环，若左边界小于右边界则正常运行，当左边界大于右边界时不符合逻辑则推出。
每次对比所要查找的值与中间下标对应的值，若所要查找的值大于中间值，则左边界下标移至中值右侧，即mid+1.否则右下标移至中间值左侧，即mid-1.
直到所要找的值与中间值相同，返回中间值，即查找成功。
若未找到，即左边界大于等于右边界，则查找无果，退出循环返回-1。
4.算法时间及空间复杂度：
时间复杂度：每次查找折半，即执行一次while循环，设共有n个数，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2^k取整后>=1，即令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)
空间复杂度：该算法使用的辅助空间仅有一个数组，所以为O（1）
5.心得体会：
起初输出总有问题，后来查找问题的时候才发现把输出语句写在了条件之外，非常粗心。
对于二分查找的边界问题起初不清晰，没有理解左右边界互换时产生的问题。