C语言实现二分查找时始终返回FALSE的问题排查

问题描述 #

参照维基百科伪代码实现的C语言二分查找程序，哪怕用仅含1个元素的数组测试也始终返回false，无法定位问题。该场景为编程挑战题目，测试套件非本人编写。

测试逻辑 #

int arr[] = {6};
size_t length = sizeof(arr)/sizeof(*arr);
TEST_ASSERT((&arr[0] == binary_search(6, arr, length)));

初始错误代码 #

int *binary_search(int value, const int *arr, size_t length) {
    int L = 0;
    int R = length - 1;
    static int m;
    while(L <= R) {
        m = floor((L + R) / 2);
        if(arr[m] < value) {
            L = m + 1;
        } else if(arr[m] > value) {
            R = m - 1;
        } else { return (&m); }
    }
    return 0;
}

错误原因 #

• 最核心错误：匹配到目标值时返回了下标变量m本身的内存地址，而非数组中对应下标的元素地址&arr[m]，两个地址完全无关，必然无法通过断言。
• 冗余逻辑：L、R均为正整数，整数除法默认向零取整，和floor效果完全一致，额外调用floor属于多余操作，还可能引入浮点数转换开销。
• 类型不匹配：函数形参arr是const int*类型，返回值为int*类型，会直接丢弃const限定符，触发编译报错或警告。
• 额外可优化点：下标变量m不需要加static修饰，静态变量会导致函数不可重入，多线程或者嵌套调用场景下会出现逻辑错误。

修复后可正常运行的代码 #

int *binary_search(int value, int *arr, size_t length) {
    int L = 0;
    int R = length - 1;
    int m;
    while(L <= R) {
        m = (L + R) / 2;
        if(arr[m] < value) {
            L = m + 1;
        } else if(arr[m] > value) {
            R = m - 1;
        } else {
            return &arr[m];
        }
    }
    return 0; // 未找到目标值
}

内容的提问来源于stack exchange，提问作者J3ck_Budl7y