使用<vs. using <=进行二进制搜索

Question

在二进制搜索中,我们通常有低变量和高变量,通常有一个while循环测试低<=高,如此代码(来自维基百科)所示:

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;
}

在学习二进制搜索时,我总是被教导低<=高的方法,但是当看到其他实现时,我看到很多人都在做(低<高).

一个对另一个有优势吗？在我自己的原生实现中,我执行<=方法,但是当我将其切换为<时,搜索失败.

使用一个与另一个有经验法则吗？

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 - 您想在列表中搜索2 [1, 2].在这种情况下,start = 0,end = 1.算法将设置mid = (0+1)/2=0为C.因此arr[mid] < key.它会start = 1, end = 1.同样,如果你在这里停止循环,算法将返回-1而不是1.

并且可能还有许多其他例子.

祝你今天愉快

Answer 2

因为low <= high，high被认为是包含的（high是我们考虑的范围的一部分）。

因为low < high,high被认为是排他性的（high不是我们考虑的范围的一部分）。

两者都可以是正确的，但在其余代码中会有细微差别，特别high是如何初始化（high = length-1vs high = length）以及如何更新（high = mid-1vs high = mid）。

哪一个更好？

主要区别在于mid = (low + high) / 2每种情况都会略有不同。

更具体地说，high在互斥情况下将大 1，因此，当high-low在包含情况下为偶数mid时，将保持不变，但high-low在包含情况下为奇数时mid，在互斥情况下将大 1 个元素（这是因为四舍五入）。

让我们考虑一个例子：

length = 6
low = 0
highInclusive = 5, highExclusive = 6
midInclusive = 5/2 = 2, midExclusive = 6/2 = 3

如您所见，当没有单个中间元素时，一个将选择左侧的元素，另一个将选择右侧的元素。

虽然这有时会使一个更快，有时会使另一个更快，但平均运行时间几乎相同。

从可读性的角度来看，在基于 0 的数组的语言中使用唯一的一个，在基于 1 的数组的语言中使用唯一的一个可能会更好（在我看来），以最小化-1代码中的's数量. 也可以提出一个论点，即在所有语言中都只使用一个版本，这样就不需要人们理解两个版本或在两者之间混淆。