算法第二章上机实验报告

1. 实践题目

   7-2 改写二分搜索算法 （20 分）

   题目来源：《计算机算法设计与分析》，王晓东

   设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

2. 问题描述      通过
3. 算法描述       在二分搜索的基础上，输出搜索结束时的left 和 right即为题目中需要输出的i和j

   int Bisearch(int a[], int left, int right, int x){
   int i=0;
   int j=0;
   while(left<=right){
   int mid = (left + right)/2;

   if(x == a[mid]) {
   i=j=mid;
   cout<<i<<" "<<j<<endl;
   return mid;
   }
   if(x > a[mid])
   left = mid +1;
   else
   right = mid - 1;
   
   }
   i = right ;
   j = left;
   cout<<i<<" "<<j<<endl;
   return -1;
   }

4. 算法时间及空间复杂度分析（要有分析过程）该算法只是在二分搜索的基础上加上了输出，因此时间复杂度为O(nlogn)

　　  5. 心得体会（对本次实践收获及疑惑进行总结）

　　　　在做这道题目时，一开始想到的是另外通过比较得出结果。但是并不符合题目的要求，因此重新考虑了二分搜索算法，注意到了搜索过程中left和right变量的数值改变可以从新利用。因此在以后的编程过程中，会注意一些变量的利用，从而减少繁杂的计算。