1、实践题目：

　改写二分搜索算法

 2、问题描述：

　设数组a[0:n-1]已排好序，输入一个整数x。

　①当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。

　②当x在数组中时，i和j相同，均是x在数组中的位置。

　输入：第一行是n值和x值，第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。

　输出：小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时，i和j相同。

　提示：若x小于全部数值，则输出：-1 ， 若x大于全部数值，则输出：n-1的值，n的值

3、算法描述：

　1）定义两个函数，主函数main()和二分搜索算法函数BinarySearch()。在函数BinarySearch()中，定义关键字key表示要查找的值x，定义一个长度为n的数组a[n]。

　2）利用二分搜索的思想，在数组中查找关键字key。当left<=right，如果key==a[mid]，则表示x在数组中，返回下标i，j，如果key>a[mid]，则left=mid+1，如果key<a[mid]，则 right=mid-1，不断减半、循环，缩小范围查找，直到left>right，如果还是没有找到x，则把right赋值给i，left赋值给就j，然后返回下标i，j。

　3）返回小于x的最大元素位置i和大于x的最小元素位置j。

4、算法部分代码：

1 int BinarySearch(int a[], int key, int n) { 2     int left = 0, right = n - 1; 3     int i = 0, j = 0; 4     while (left <= right) { 5         int mid = (left + right) / 2; 6         if (key == a[mid]) 7         { 8             i = j = mid; 9             cout << i <<" "<
     
      <
      
        a[mid]) left = mid + 1;13         else { right = mid - 1; }14     }15      i = right;16      j = left;17     cout << i<<" "<< j<
      
     

5、算法时间复杂度和空间复杂度：

　①时间复杂度：循环体每循环一次时间复杂度减少一半，而且判断的时间复杂度为O(1),所以根据公式得算法时间复杂度为T(n)=1*T(N/2)+O(1)=O(logn)

　②空间复杂度：各个变量的空间复杂度都是O(1)，申请了n个空间，所以算法空间复杂度为O(n)

 6、心得体会：

　经过这次小组上机实践，我对于二分搜索算法有了更深刻的了解。在一开始，我和队友直接采用非二分法的方法，导致时间复杂度不符合要求，后来经过老师提醒和队友间的合作，最终完成了任务。二分搜索在while循环体内，每次将查找的范围缩小一半，循环、判断、减半，直到最后找到记录或者找不到记录时返回。该算法简洁明了，以后会多学习和练习类似的算法。