java - 使用 start < end 与使用 start <= end 的二分查找

Question

在二分搜索中，我们通常有 low 和 high 变量，并且通常有一个 while 循环来测试 low <= high，如以下代码所示(来自维基百科):

int SortedArray[max] = {....}

int BinarySearch (int key)
{
    int start = 0;
    int end = max - 1;
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (key == a[mid])
            return mid;
        else if (key < a[mid])
            end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

在学习二分查找时，我总是被教导 start <= end 方法，但是当看到其他实现时，我看到很多人都这样做 while(start < end)。

两者相比是否有优势？在我自己的 native 实现中，我使用 <= 方法，但是当我将其切换为 < 时，搜索失败。

是否有使用其中一种与另一种的经验法则？

Answer 1

即使你的问题可能不是很清楚，我也可以推断你正在谈论这种二分搜索的实现(这里用 C 语言，来自维基百科):

int SortedArray[max] = {....}

int BinarySearch (int key)
{
    int start = 0;
    int end = max - 1;
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (key == a[mid])
            return mid;
        else if (key < a[mid])
            end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

如果替换 start <= end通过start < end ，在某些情况下你的算法不会给出好的答案。

让我们考虑两种情况。

1 - 您想要在列表 [1] 中搜索 1 。在这种情况下，start = 0, end = 0如果更改循环条件，算法将返回 -1。

2 - 您想要在列表 [1, 2] 中搜索 2 。在这种情况下，开始 = 0，结束 = 1。算法将设置 mid = (0+1)/2=0在C中。因此arr[mid] < key 。它将使得start = 1, end = 1 。同样，如果您在此处停止循环，算法将返回 -1 而不是 1。

可能还有很多其他例子。

祝你有美好的一天