混淆二进制搜索何时使用 left < right ；左<=右；还有更多

Question

我很难理解何时使用：

while (left < right ) {
}

与何时使用：

while (left <= right ) {
}

此外，有时我们在设置左右边界时使用：

left = mid

有时我们使用

left = mid + 1;

类似

right = mid; vs
right = mid - 1;

二分查找的知识中是否缺少任何基础知识？

Answer 1

划分数组时，您会找到 mid 索引。此时您有两个具有 mid 索引的部分。由于数组已排序，您可以将搜索元素与 mid 索引值进行比较。

如果搜索值小于 mid 索引值，您知道它在左侧，否则它在右侧。

现在，您对左半部分（索引 0 到 mid - 1）或右半部分（索引 mid +1 到结束）重复上述步骤（分为两部分，中间索引等）。如果搜索值与 mid 索引值相同，则找到元素并停止处理。

此划分和比较过程将继续，直到您找到搜索元素或左右索引（最初为 0 且长度为 1）重叠。这就是条件 left <= right.

的原因

Answer 2

基本思路是搜索并找到元素：

public static int indexOf(int[] array, int target) {
   int lo = 0, hi = a.length - 1;
   while (lo <= hi) {
      // Key is in a[lo..hi] or may be it is not present.
      int mid = lo + (hi - lo) / 2;
      if      (target < a[mid]) hi = mid - 1;
      else if (target > a[mid]) lo = mid + 1;
      else return mid;
   }
   return -1;
}

我们也可以使用 mid = (lo + hi) >>> 1 来计算中间值，但是使用 (lo+hi)/2 可能会导致溢出。现在是混淆部分：

We use while (lo <= hi) if we are returning the match from inside the loop. We use while (lo < hi) when we want to exit the loop first and then use the result of lo or hi to return the match.

Answer 3

使用左 <= 右当您更改循环中的中间索引时

 mid = right -1
 mid = left +1

使用左 < 右当您将左右直接分配给 mid

right = mid
left = mid+1

混淆二进制搜索何时使用 left < right ；左<=右；还有更多

Confuse in Binary Search when to use left < right ; left <= right ; and few more

binary-search