顺序映像实现折半查找

Question

第9章 查找
1、（折半查找）：用顺序映像实现折半查找算法（即二分查找算法），可自选递归或非递归方式；具体要求如下：
在主函数中用rand()函数（需包含“stdlib.h”头文件）产生10000个递增的随机数（相邻位置间的递增值为[0~10）之间的随机值），并输出这10000个数。然后从键盘上输入待查找的数，并调用查找函数fun（）进行查找
在fun( )函数中，按折半查找法查找指定的数，如果找到则返回它的位置序号，如果没找到则返回一个特定代码（比如 -1）
若查找成功，则将查找成功的提示和位置序号在主函数中输出；若查找失败，则将查找失败的提示在主函数中输出；
无论查找成功还是失败，都要在主函数中输出比较次数；

Answer 1

以下是 C++ 代码，其中采用非递归的方式实现折半查找算法：

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int N = 10000;
int a[N];

void generateRandomArray() {
    srand(time(0));
    a[0] = rand() % 10;
    cout << a[0] << " ";
    for (int i = 1; i < N; i++) {
        a[i] = a[i - 1] + rand() % 10;
        cout << a[i] << " ";
    }
    cout << endl;
}

int binarySearch(int x) {
    int left = 0, right = N - 1;
    int cnt = 0;
    while (left <= right) {
        cnt++;
        int mid = (left + right) / 2;
        if (a[mid] == x) {
            return mid;
        } else if (a[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    generateRandomArray();
    cout << "Enter the number you want to search for: ";
    int x;
    cin >> x;
    int pos = binarySearch(x);
    if (pos != -1) {
        cout << "The number was found at position " << pos + 1 << endl;
    } else {
        cout << "The number was not found" << endl;
    }
    cout << "Comparison times: " << cnt << endl;
    return 0;
}

在这个程序中，generateRandomArray()函数用于生成一个递增的随机数组，binarySearch()函数实现了非递归的折半查找算法，该函数查找成功时返回数的位置序号，查找失败时返回 -1。主函数在调用binarySearch()函数并输出查找结果后，还会输出比较的次数