使用start<end的java二进制搜索与使用start<=end的java二进制搜索

Question

在二进制搜索中，我们通常有低变量和高变量，通常有一个while循环来测试low<；=高，如以下代码所示（来自维基百科）：

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

可能还有很多其他的例子

祝你今天愉快

Answer 2

对于low <= high，high被视为包含（high是我们考虑的范围的一部分）

对于low < high，high被认为是独占的（high不属于我们考虑的范围）

两者都可能是正确的，但是代码的其余部分会有细微的区别，特别是high是如何初始化的（high = length-1与high = length），以及它是如何更新的（high = mid-1与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数。还可以提出一个论点，即在所有语言中只使用一个版本，而不要求人们理解两个版本或混淆两个版本