算法第二章上机实践报告

待我称王封你为后i 2021-10-01 04:24 439阅读 0赞

**1.实践题目：**

二分查找

**2.问题描述：**

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

**3.算法描述：**

1 int BIN(int a[], int key, int n) {
           //二分查找算法
     2 int left = 0;//最左
     3 int right = n - 1;//最右
     4 int t = 0;//比较次数 
     5 while (left <= right) { //当左边小于等于右边时
     6 int middle = (left + right) / 2;//中间数等于左右相加除二
     7 t++;//比较了一次
     8 if (key == a[middle])//当要查找的数字等于中间数时
     9 {
    10 cout << middle<<endl;//直接输出
    11 cout << t; 
    12 return middle;
    13 }
    14 if (key > a[middle]){
           //当要查找的数大于中间数时
    15 
    16 left = middle + 1;}//左边移到中间加一
    17 
    18 else { right = middle - 1; }//否则右边移到中间减一
    19 
    20 }
    21 cout << "-1"<< endl;//当查找的数不在查找区间内时输出-1
    22 cout << t ;//循环结束输出次数t
    23 }

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

时间复杂度最坏情况下是O(logn)：因为最坏情况下while循环执行了logn次

最好情况下是O(1):因为最好情况下while循环执行了1次

空间复杂度是O(1)：因为只有一个循环

**5.心得体会**

本次实践让我更加清楚了二分查找的算法过程，并且在结对编程的过程中也能互相学习。且在上机实践的过程中发现自己对return的用法有疑惑，对什么情况需要return不是特别熟悉，在老师检查时因在cout了-1之后又return了-1而被提问，后发觉并不需要return -1，此为多此一举。后来去认真地学习了return的用法，发现return语句用于结束当前正在执行的函数，并将控制权返回给调用此函数的函数。且return语句有两种表示形式：一种是具有返回值的函数（任何返回类型不是void的函数都必须返回一个值，而且这个返回值的类型必须和函数的返回类型相同，或者能隐式转化为函数的返回类型。尽管C++不能确保结果的正确性，便能保证函数每一次return都返回适当类型的结果），一种是没有返回值的元素（不带返回值的return语句只能用于返回类型为void的函数，return语句是为了引起函数的强制结束，这种用法类似于循环结构中的break语句的作用）。而在我的代码中不属于以上类型，无需返回值。

转载于:https://www.cnblogs.com/VKookie/p/9786790.html