c - 如何实现整数数组的二进制搜索？

Question

我想对一个整数数组进行二分查找。我确保数组是递增排序的。但是我的功能并没有跟踪所有的案例，一些检查失败了。我在这里错过了什么？Value 代表我要查找的整数。

bool search(int value, int array[], int n)
{   
    int left = 0;
    int right = n - 1;
    int middle = (left + right) / 2;

while (right >= left)
{
    if (array[middle] == value)
    return true;
    else if (array[middle] < value)
    right = middle;
    else if (array[middle] > value)
    left = middle + 1;

    middle = (left + right) / 2;
}

return false;
} 

我的猜测是无法预测某些左边界或右边界情况。我也不喜欢 while 条件。

Answer 1

你左右混了，如果array[middle] < value你必须改变left .

bool search(int value, int array[], int n)
{
    int left = 0;
    int right = n - 1;
    int middle = left + (right - left) / 2;

    while (right >= left)
    {
        if (array[middle] == value)
            return true;
        else if (array[middle] > value)
            right = middle - 1;
        else if (array[middle] < value)
            left = middle + 1;

        middle = (left + right) / 2;
    }
    return false;
}

将工作:http://ideone.com/VSAhnZ

进一步的改进可以是:

1. 您可以排除 middle在else部分，因为你已经证明它不是正确的值 ( right = middle; => right = middle - 1; )

2. 第二个else if可以用 else 代替.如果它不是该值并且不小于您不必测试它是否更大。