C中的二进制搜索总是返回FALSE

二进制搜索（Binary Search）是一种高效的查找算法，适用于已排序的数据集。它的基本思想是通过逐步缩小查找范围来快速定位目标值。下面我将详细解释二进制搜索的基础概念、优势、类型、应用场景，并分析为什么在C语言中可能会遇到总是返回FALSE的问题，以及如何解决这些问题。

基础概念

二进制搜索的工作原理如下：

初始化：设定两个指针，low 和 high，分别指向数组的起始和结束位置。
循环查找：在每次循环中，计算中间位置 mid，并比较中间位置的值与目标值。
调整范围：
- 如果中间值等于目标值，返回 TRUE 或相应的索引。
- 如果中间值大于目标值，将 high 更新为 mid - 1。
- 如果中间值小于目标值，将 low 更新为 mid + 1。

终止条件：当 low 超过 high 时，表示未找到目标值，返回 FALSE。

优势

时间复杂度：O(log n)，比线性搜索快得多。
适用性：仅适用于已排序的数据集。

类型

迭代实现：使用循环进行查找。
递归实现：通过函数递归调用自身进行查找。

应用场景

数据库索引查找。
大型数据集的快速检索。
算法竞赛中的常用技巧。

可能的问题及解决方法

问题：C中的二进制搜索总是返回FALSE

这通常是由于以下原因之一造成的：

数据未排序：二进制搜索的前提是数据必须已排序。
边界条件处理不当：可能导致无限循环或提前退出。
整数溢出：在计算 mid 时可能发生整数溢出。

示例代码及解决方法

以下是一个正确的二进制搜索C语言实现示例：

#include <stdio.h>
#include <stdbool.h>

bool 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 true;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return false;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;

    if (binarySearch(arr, size, target)) {
        printf("Element found\n");
    } else {
        printf("Element not found\n");
    }

    return 0;
}