第二章实践报告

实践题目：7-1
问题描述：使用二分查找算法在n个非降序排列的整数中查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
算法描述：将n个元素分成个数大致相同的两半，取a[mid]与x比较。如果x=a[mid]，则找到x，算法终止；如果x<a[mid]，则只在数组a的左半部继续查找x，如果x>a[mid]，则只在a的右半部继续搜索x。同时，在while语句里加一个b统计比较次数。

代码实现：

 1 #include<iostream>
 2 using namespace std;
 3 int BinarySearch(int a[],int left,int right,int x,int &b){
 4     while (left<=right){
 5         b++；
 6         int middle =(left+right)/2;
 7         if (x==a[middle]){
 8             return middle;
 9         }
10         if(x>a[middle]){
11             left=middle+1;
12         }
13         else {
14             right =middle-1;
15         } 
16     }
17     return -1;
18 }
19 int main(){
20     int n,x,b=0;
21     cin>>n;
22     int a[1000];
23     for (int i=0;i<n;i++){
24         cin>>a[i];
25     }
26     cin>>x;
27     int index=BinarySearch(a,0,n-1,x,b);
28     cout<<index<<endl<<b;
29 }

时间复杂度和空间复杂度:用了二分法搜索算法，寻找x的时间复杂度为O(logn)；空间复杂度为数组空间大小，是一个常数，与变量n的取值无关。所以空间复杂度为O(1)。
心得体会：一开始的时候我是把“b++;”这个语句放在每一个if判断后的，经过老师的提醒才想到原来可以就放在while函数里就好，不用重复三次。可以让代码变得更简洁，以后编程或者做题的时候，能简洁就尽量简洁。还有，编程习惯，代码风格真的很重要，这是我以后要改进的地方。