int BinarySearch(int a[],int x, int n){//在数组a[i]中查找X，找到返回X在数组的位置，否则返回-1 int left = 0; int right = n-1; int count = 0;//设数组位置左边为0；右边为n-1;定义count为比较次数变量。 while(left<=right){ int middle = (left+right)/2;//取中间的值 count++;//比较次数加1 if (x == a[middle]) { cout << middle <<endl;//输出下标 cout << count;//输出比较次数 return middle; } if (x > a[middle]) left = middle + 1; else right = middle - 1; }//二分搜素思想 cout << "-1" <<endl; cout << count <<endl; return -1; }//x不存在时的输出
算法时间及空间复杂度分析（要有分析过程）：每执行一次while循环，待搜索数组大小减小一半，最多可能执行O（logn）次，循环体内为O（1）次，则时间复杂度为O（logn），该算法需要一个大小为n的空间辅助数组，所以空间复杂度为O（n）.
心得体会（对本次实践收获及疑惑进行总结）：这一次实验三道题中，这道题的算法是最简单的，也是最容易理解的，但也花了不少时间，主要难点在于输出他的比较次数上，最后多设一个变量进行累加就完成了；算法虽简单，但写出来还是会经常出错，得加强平时练习，熟悉算法与语法。
转载于:https://www.cnblogs.com/kop126/p/9788865.html
