随机产生80个整数构成的递增序列,使用折半查找算法查找指定的整数,并统计比较次数。提示:可用 a[i] = a[i-1] + rand() % 10 + 1产生递增序列。

下面是使用C++实现的代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int binarySearch(int arr[], int n, int target, int& count) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        count++;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    srand(time(NULL)); // 用当前时间作为随机数种子
    const int N = 80; // 数组长度为80
    int arr[N];
    arr[0] = rand() % 100; // 第一个数随机生成
    for (int i = 1; i < N; i++) {
        arr[i] = arr[i - 1] + rand() % 10 + 1; // 递增序列
    }
    int target = arr[rand() % N]; // 随机选择一个数作为要查找的目标
    int count = 0; // 统计比较次数
    int idx = binarySearch(arr, N, target, count);
    if (idx != -1) {
        cout << "找到了，下标为" << idx << endl;
    } else {
        cout << "没找到" << endl;
    }
    cout << "比较次数：" << count << endl;
    return 0;
}

运行结果示例：

找到了，下标为54
比较次数：7