算法第二章上机实践报告

一.实践题目

输入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

 

 

二.问题描述　　

由n个非降序排列的整数组成的数列，查找输入的x是否存在于数列中，存在则输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

 

 

三.算法描述

通过二分查找找到数列中间位置的数与x进行比较，如果x小于该数列中间位置的数，则该数列中间位置的数的左边所有数组成新的数列，若x大于该数列中间位置的数，则该数列中间位置的数的右边所有数组成新的数列，然后重复上面的操作，直到找到x或查找完数列。若x存在则x所在的下标（0~n-1）及比较次数，若x不存在，输出-1和比较次数。　　

 代码：

#include <iostream>
using namespace std;
int a[10005] = {};
static int num ,xiabiao;

void binarySearch(int* a , int k , int left ,int right);

int main() {
    int n = 0 , x = 0;
    cin >> n;
    for (int i = 0; i < n ; i ++) {
        cin >> a[i];
    }
    cin >> x;
    binarySearch(a , x , 0 , n - 1);
    cout << xiabiao << endl << num ;
} 

void binarySearch(int* a , int k, int left ,int right) {
    if (left > right)
        return;
    int mid = (left + right) / 2;
    num ++;
    if (k != a[mid]) {
        xiabiao = -1;
        if (k > a[mid]) {
            binarySearch(a , k , mid + 1 , right);
        } else{
            binarySearch(a , k , left , mid - 1);
        }    
    }
    else 
        xiabiao = mid;
            
}

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

由于每比较一次中位数，数列的大小减为一半，消耗时间为O（log n），其他操作所需时间都为常数时间，所以时间复杂度为O（log n）。

另外算法执行时所需的辅助空间与问题规模 n 无关，所以空间复杂度为O（1）。

五.心得体会

这是二分查找的经典运用，递归结束条件的判断是关键，通过这道题我更加熟悉二分查找