迭代实现二分查找查询三类目标值（低中/中高区间/不存在最高值）

需求说明 #

需要实现迭代式二分查找，依次输出三类目标值的查询结果：

• 第一类：位于数组低索引与初始mid索引区间的存在值
• 第二类：位于数组初始mid索引与高索引区间的存在值
• 第三类：数组中不存在的最大值

实现逻辑 #

基于二分查找要求数组有序的前提，采用迭代流程实现功能：

1. 接收用户输入的升序数组、数组长度
2. 依次读取三类待查询的目标值单独存储
3. 对每个目标值分别执行一次迭代二分查找，输出对应查询结果

注：你提供的参考代码存在两处缺陷：三次读取目标值都存入同一个变量，前两次输入会被最后一次覆盖；仅执行了一次二分查找逻辑，只能得到第三个目标值的查询结果。以下为修正后的可运行代码。

完整实现代码 #

#include <stdio.h>

// 迭代式二分查找：输入升序数组、数组长度、目标值，直接打印查询结果
void binary_search(int array[], int n, int search) {
    int first = 0, last = n - 1, middle = (first + last) / 2;
    while (first <= last) {
        if (array[middle] < search) {
            first = middle + 1;
        } else if (array[middle] == search) {
            printf("%d found at location %d.\n", search, middle + 1);
            return;
        } else {
            last = middle - 1;
        }
        middle = (first + last) / 2;
    }
    printf("Not found! %d isn't present in the list.\n", search);
}

int main()
{
    int c, n, array[100];
    int targets[3]; // 分别存储三类待查询目标值

    printf("Enter number of elements\n");
    scanf("%d", &n);

    printf("Enter %d integers in ascending order\n", n);
    for (c = 0; c < n; c++) {
        scanf("%d", &array[c]);
    }

    printf("Enter first value to find (in low ~ mid index range)\n");
    scanf("%d", &targets[0]);
    printf("Enter second value to find (in mid ~ high index range)\n");
    scanf("%d", &targets[1]);
    printf("Enter third value to find (maximum value not in array)\n");
    scanf("%d", &targets[2]);

    // 依次执行三次查询
    for (int i = 0; i < 3; i++) {
        binary_search(array, n, targets[i]);
    }

    return 0;
}

运行示例 #

以长度为8的升序数组[1,3,5,7,9,11,13,15]为例，初始mid索引为(0+7)/2=3，对应值为7，刚好划分高低区间：

输入 #

8
1 3 5 7 9 11 13 15
3
11
17

输出 #

3 found at location 2.
11 found at location 6.
Not found! 17 isn't present in the list.

内容的提问来源于stack exchange，提问作者Zulkar Nain Sayeed