C语言实现折半查找法（二分法）

折半查找法也叫做二分查找，顾名思义，就是把数据分成两半，再判断所查找的key在哪一半中，再重复上述步骤知道找到目标key; 注意：折半查找法仅适用于对已有顺序的数组、数据进行操作！！！ 很显然，折半查找法相对于其他查找方法例如顺序查找法效率要高很多； 下面我们来实际操作一下，了解二分查找的奥义。 例如：要在数组arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置；首先，我们要先将数组arr中的数据成员进行排序。arr[]={1,2,3,4,5,6,7,8,9,10,11}; 如图所示：将该组数据小端记作low，大端记作high,中间值记作mid; 二分法查找 二分查找，又称折半查找，是一种在有序数组或列表中高效寻找特定元素的搜索算法。它的基本思想是将待查找的元素与数组中间位置的元素进行比较，根据比较结果来决定是在数组的左半部分还是右半部分继续查找。通过不断缩小查找范围，直到找到目标元素或者确定元素不存在为止。 在上述的C语言实现中，`BinSearch`函数是二分查找的核心。它接收三个参数：一个已排序的整型数组`arr`，数组的长度`len`，以及要查找的目标值`key`。初始化`low`为0，表示数组的起始位置，`high`为`len - 1`，表示数组的结束位置。`mid`用于存储每次查找的中间值。 在`while`循环中，计算`mid`的值，即`(low + high) / 2`。然后，通过比较`key`与`arr[mid]`，判断查找区间： 1. 如果`key`等于`arr[mid]`，则找到了目标元素，返回`mid`作为其索引。 2. 如果`key`大于`arr[mid]`，那么目标元素可能在`mid`的右边，因此更新`low`为`mid + 1`。 3. 如果`key`小于`arr[mid]`，则目标元素可能在`mid`的左边，因此更新`high`为`mid - 1`。 当`low`大于`high`时，说明已经遍历完整个数组但未找到目标元素，此时返回-1表示未找到。 需要注意的是，计算`mid`时，如果`(low + high)`的结果不是整数，应当考虑进行取整操作，确保`mid`的正确性。在上述代码中， `(low + high) / 2`会自动进行整数除法，所以不需要额外处理。 在`main`函数中，我们创建了一个已排序的数组`arr`并调用`BinSearch`函数查找`key=7`的位置，最后打印出结果。执行这段代码，将输出查找结果，即`key=7`的索引。 二分查找的优势在于其时间复杂度为O(log n)，相比线性的顺序查找（时间复杂度O(n)），在大规模数据查找时，二分查找能显著提高效率。但必须强调的是，二分查找只适用于有序的数据结构，因此在使用前，确保数据已排序至关重要。