C语言实现折半查找的递归和非递归算法

折半查找，也称二分查找，是一种基于比较的查找算法。它的时间复杂度为 O(log n)，适用于有序的线性结构（如数组、有序列表等）。

非递归算法实现折半查找：

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

递归算法实现折半查找：

int binary_search(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binary_search(arr, mid + 1, right, target);
        } else {
            return binary_search(arr, left, mid - 1, target);
        }
    }
    return -1;
}

其中，arr 为有序数组，n 表示数组长度，target 表示要查找的值。非递归算法使用 while 循环实现，递归算法使用函数递归实现。