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

Question

C语音数据结构与算法，给出若干个整数询问其中是否有一对数的和等于给定的数

Answer 1

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

在C语言中，我们可以使用二分查找（Binary Search）的方法来实现这个功能。二分查找适用于已经排序的数组。这里是一个简单的示例程序，它会读取输入的数组长度、查找目标以及数组元素，然后执行二分查找并返回索引和查找次数。

首先，我们需要定义一个函数binary_search()来进行二分查找，然后在主函数main()中处理输入和调用这个函数。

以下是完整的C语言代码实现：

#include <stdio.h>

int binary_search(int arr[], int target, int low, int high, int *count) {
    if (low > high) {
        return -1; // 没有找到目标值
    }
    
    int mid = (low + high) / 2;
    (*count)++;
    
    if (arr[mid] == target) {
        return mid; // 找到目标值
    } else if (arr[mid] < target) {
        return binary_search(arr, target, mid + 1, high, count); // 在右半部分查找
    } else {
        return binary_search(arr, target, low, mid - 1, count); // 在左半部分查找
    }
}

int main() {
    int length, target, elements[100], i, index = -1, count = 0;

    printf("请输入数组长度：");
    scanf("%d", &length);

    printf("请输入要查找的目标值：");
    scanf("%d", &target);

    for (i = 0; i < length && scanf("%d", &elements[i]) != EOF; i++) {}

    if (scanf("%*s") == EOF) { // 跳过换行符
        elements[i] = 0; // 添加一个结束标记
    }

    // 对数组进行排序，这里使用快速排序作为例子
    quicksort(elements, 0, i-1);

    index = binary_search(elements, target, 0, i-1, &count);

    if (index != -1) {
        printf("索引值：%d\n查找次数：%d\n", index, count);
    } else {
        printf("No\n");
    }

    return 0;
}

// 快速排序函数，这里仅作排序之用，实际应用中可以使用系统库中的排序函数
void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot - 1);
        quicksort(arr, pivot + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

在这个代码中，我们首先读取数组长度和目标值，然后读取数组元素。接下来，我们对数组进行排序，这里使用了快速排序算法。之后，我们调用binary_search()函数进行查找，并将结果存储在变量index和count中。最后，根据index的值输出相应的信息。

注意，由于题目没有提供快速排序的实现，这里为了简化示例，我添加了一个快速排序函数。在实际应用中，你可以使用标准库提供的排序函数，例如qsort()。

此代码段仅处理了一次查找，如果你想要扩展为查询多个目标值，可以在main()函数中增加循环来处理这种情况。