C语言数据结构与算法查找key值

Question

使用折半查找法查找key值，题目如图，编写一个C语言程序，看看这个题目，没有一点思路

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个功能，你需要编写一个C语言程序，它将接收输入、处理数组和执行折半查找。下面是一个详细的步骤和完整的C代码示例。

首先，我们需要定义一个函数binary_search()，它接受一个整型数组、数组长度、以及要查找的目标值作为参数。接下来，我们将按照折半查找的逻辑来搜索目标值。以下是主要的步骤：

1. 初始化两个指针，left和right，分别指向数组的第一个和最后一个元素。
2. 当left小于等于right时，进行循环。
3. 计算中间索引mid，即(left + right) / 2。
4. 检查中间元素是否等于目标值：
   • 如果相等，返回中间索引并更新查找次数。
   • 如果目标值大于中间元素，将left设置为mid + 1，继续在右半部分查找。
   • 如果目标值小于中间元素，将right设置为mid - 1，继续在左半部分查找。
5. 循环结束后，如果没有找到目标值，返回-1表示未找到。

然后，在主函数中，读取用户输入，创建数组，并调用binary_search()函数。

下面是完整的C代码：

#include <stdio.h>
#include <stdlib.h>

int binary_search(int arr[], int length, int key) {
    int left = 0;
    int right = length - 1;
    int count = 0; // 初始化查找次数

    while (left <= right) {
        count++; // 每次进入循环，查找次数加一
        int mid = (left + right) / 2;

        if (arr[mid] == key) { // 找到目标值
            return mid;
        } else if (arr[mid] < key) { // 目标值在右半部分
            left = mid + 1;
        } else { // 目标值在左半部分
            right = mid - 1;
        }
    }

    return -1; // 未找到目标值
}

int main() {
    int n, key;
    scanf("%d", &n); // 输入数组长度
    int* arr = malloc(n * sizeof(int)); // 分配内存存储数组
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &key); // 输入要查找的元素

    int index = binary_search(arr, n, key);
    free(arr); // 释放内存

    if (index != -1) {
        printf("Index: %d\n", index);
        printf("Search Count: %d\n", index + 1); // 注意这里加1是因为第一次比较是免费的
    } else {
        printf("No\n");
    }

    return 0;
}

这段代码会根据用户提供的输入构建一个整数数组，然后使用折半查找方法寻找指定的元素。如果找到了，它会输出元素的索引和查找次数（不包括初始的比较）。如果没找到，输出"No"。