C语言实现折半查找算法：详解与示例代码

#include <stdio.h>

// 折半查找算法
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    
    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 12;
    
    int result = binarySearch(arr, n, target);
    
    if (result == -1) {
        printf('Element not found\n');
    }
    else {
        printf('Element found at index %d\n', result);
    }
    
    return 0;
}

运行结果：

Element found at index 5

代码解析：

1. 函数binarySearch: 接受一个有序数组arr、数组长度n和目标值target作为参数。
2. 循环查找: 使用while循环，当左边界left小于等于右边界right时执行查找。
3. 计算中间位置: 在每次迭代中，计算中间位置mid。
4. 比较: 将目标值target与中间元素arr[mid]进行比较：
   • 如果相等，则找到目标值，返回索引mid。
   • 如果目标值小于中间元素，则在左半部分继续查找，更新right为mid - 1。
   • 如果目标值大于中间元素，则在右半部分继续查找，更新left为mid + 1。
5. 未找到: 如果循环结束仍未找到目标值，则返回-1表示查找失败。

总结：

折半查找是一种高效的搜索算法，适用于有序数组。其时间复杂度为O(log n)，比线性搜索更快。本示例代码演示了如何使用C语言实现折半查找算法，并提供了详细的代码解析和运行结果。