二分查找c语言版函数

#### 引言 在算法的世界中，二分查找法是一种高效且广泛应用的搜索算法，它的核心思想是将一个有序数组分成两部分，通过比较目标值与中间元素的大小，逐步缩小搜索范围，直至找到目标值或确定目标值不存在于数组中。这种方法的时间复杂度为(O(\log n))，相较于线性搜索的(O(n))，效率大大提高。

二分查找法的定义与条件

二分查找法，又称折半查找法，是一种在有序数组中查找特定元素的算法。它依赖于以下条件：

1. 数组必须是有序的。
2. 查找过程是迭代进行的。

二分查找法与线性查找法的对比

二分查找法在有序数组中表现卓越，但在无序数组中无法使用。而线性查找法则对数组的有序性没有要求，但效率较低。

核心类与方法

二分查找法的核心在于两个操作：

1. 确定中间位置：( mid = \frac{low + high}{2} )。
2. 根据中间元素与目标值的比较结果，更新搜索区间。

使用场景

二分查找法适用于任何有序集合中快速定位元素的场景，如数据库索引、文件系统查找等。

代码案例一：标准二分查找法

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (arr[mid] == x)
            return mid;

        if (arr[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }

    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? printf("Element is not present in array") : printf("Element is present at index %d", result);
    return 0;
}

代码案例二：改良的二分查找法

改良的二分查找法在标准二分查找法的基础上，通过引入一个标志变量来优化代码的可读性。

#include <stdio.h>

int binarySearchImproved(int arr[], int l, int r, int x) {
    int mid;
    while (l <= r) {
        mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearchImproved(arr, 0, n - 1, x);
    (result == -1) ? printf("Element is not present in array") : printf("Element is present at index %d", result);
    return 0;
}

相关知识点补充

使用表格来补充二分查找法的相关知识点：

通过上述的讲解和代码案例，我们可以更深入地理解二分查找法在C语言中的应用和实现。