算法第二章上机实践报告

1.实践题目

二分查找

2.问题描述

输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入格式:

输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。

输出格式:

输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入样例:

4
1 2 3 4
1

输出样例:

   0

   2

3.算法描述

定义两个变量left和right记录每次查找区间的最左和最右两个数的下标

判断每次查找区间的中间数与需要查找的数的大小，中间数比查找数大时用right记录中间数的下标，left不变。中间数比查找数小时用left记录中间数的下标，right不变。在left和tight之间再次查找。直到中间数等于要查找的数，查找结束，或者未查找到要查找的数。

代码

#include <iostream>
using namespace std;

int binarysearch(int *a, int n, int key, int &count){
     int left = 0;
     int right = n-1;

     while(left <= right){
     int mid = (left + right)/2;
     count++;
     if(key == a[mid]){
     return mid;
     }
     else if(key < a[mid]){
     right = mid - 1;
     }
     else
     {
     left = mid + 1;
     }

     }
    return -1;
     }

int main(){
int n , key;
int count = 0;
int *a = new int [1000];
cin>>n;
for(int i = 0; i < n; i++){
cin>>a[i];}
cin>>key;

int median = binarysearch(a, n, key, count);

cout<<median<<endl;
cout<<count;
return 0;
}

4.算法时间及空间复杂度分析

算法每执行一次while循环，需要搜索的数组大小减一半，在最坏情况下，while循环被执行了O（log n）次。而在循环体内执行需要O（1）时间，所以整个算法的时间复杂度为O（log n）

由于每一次查找都在同一个数组空间进行，所以空间复杂度为O（1）

5.心得体会

整个算法，关键是需要理解二分查找的查找原理。

同时，通过binarysearch函数引用变量count记录比较次数。