为什么我的二进制搜索实现没有找到最后一个元素？

Question

我已经用C语言实现了二分查找的初学者递归版本。但是，当要查找的元素位于数组的最后一个位置时，它似乎不起作用。有没有办法在不改变函数原型的情况下解决这个问题？

#include <stdio.h>

int search(int value, int values[], int n);

int main() {
    int a[] = { 26, 27, 28 };

    if (search(28, a, 3) == 0)
        printf("Found.\n");
    else
        printf("Not found.\n");
}

int search(int value, int values[], int n)
{
    if (n <= 0) 
        return 1;

    if (value < values[n/2])
        // Search the left half
        return search(value, values, n/2);
    else if (value > values[n/2])
        // Search the right half, excluding the middle term
        return search(value, values + n/2 + 1, n/2 - 1);
    else 
        return 0;

    return 1;
}

Answer 1

这似乎是您在 else if 子句中的 return 语句。数组的长度 n 应该是 n-n/2-1 而不是 n/2-1 否则最后一个元素将被剪掉。随着数组长度的增加以及您正在搜索来自右侧的元素，您可以看到这种情况更加普遍。

return search(value, values + n/2 + 1, n - n/2 - 1);

注：正如 chqrlie 指出的

Answer 2

您的 search 函数不正确：

递归右侧部分时传递的切片大小计算不正确：它应该是 n - n/2 - 1 而不是 n/2 - 1。

这是更正后的版本：

#include <stdio.h>

int search(int value, int values[], int n);

int main(void) {
    int a[] = { 26, 27, 28 };

    if (search(28, a, 3) == 0)
        printf("Found.\n");
    else
        printf("Not found.\n");

    return 0;
}

int search(int value, int values[], int n) {
    if (n > 0) {
        int mid = n / 2;
        if (value < values[mid]) {
            // Search the left half
            return search(value, values, mid);
        } else
        if (value > values[mid]) {
            // Search the right half, excluding the middle term
            return search(value, values + mid + 1, n - mid - 1);
        } else {
            // Found the value
            return 0;
        }
    }
    return 1;
}

这是一个更简单的迭代版本：

int search(int value, int values[], int n) {
    while (n > 0) {
        int mid = n / 2;
        if (value < values[mid]) {
            // Search the left half
            n = mid;
        } else
        if (value > values[mid]) {
            // Search the right half, excluding the middle term
            values += mid + 1;
            n -= mid + 1;
        } else {
            // Found the value
            return 0;
        }
    }
    return 1;
}

为什么我的二进制搜索实现没有找到最后一个元素？

Why doesn't my binary search implementation find the last element?

c

arrays

binary-search