C语言折半查找（对分搜索）

折半查找，也称为二分查找或对分搜索，是一种高效的查找算法，适用于已经有序的数组。它通过不断缩小搜索范围来快速定位目标元素的位置。以下是一个使用 C 语言实现折半查找的示例代码：

#include <stdio.h>

// 折半查找函数
int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;  // 找到目标元素，返回其索引
        } else if (arr[mid] < target) {
            low = mid + 1;  // 在右半部分继续查找
        } else {
            high = mid - 1; // 在左半部分继续查找
        }
    }

    return -1;  // 没找到目标元素，返回 -1
}

int main() {
    int arr[] = {10, 22, 30, 44, 55, 65, 77, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

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

    int index = binarySearch(arr, size, target);

    if (index != -1) {
        printf("目标元素 %d 在数组中的索引为 %d\\n", target, index);
    } else {
        printf("未找到目标元素 %d\\n", target);
    }

    return 0;
}

在这段代码中，binarySearch 函数使用循环来实现折半查找。它通过比较中间元素与目标元素的大小，缩小搜索范围，直到找到目标元素或搜索范围为空为止。

折半查找的时间复杂度为 O(log n)，其中 n 是数组的大小。它是一种非常高效的查找方法，但要求数组必须是有序的。在实际应用中，如果数据量较大且已经排序，折半查找通常是一个很好的选择。