在二分查找中混淆何时使用左< right ; left <= right ; and few more

Question

我很难理解何时使用：

while (left < right ) {
}

与何时使用：

while (left <= right ) {
}

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

left = mid 

有时我们会使用

left = mid + 1;

同样

right = mid; vs
right = mid - 1;

我在二分搜索知识中是否缺少任何基础知识？

Answer 1

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

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

可能会导致溢出。现在是混乱的部分：

如果我们从内部返回匹配项，则使用

while (lo <= hi)

循环。当我们想要退出循环时，我们使用

while (lo < hi)

首先，然后使用

lo

或

hi

的结果返回匹配。

二分搜索用例的良好介绍：https://leetcode.com/discuss/general-discussion/786126/Python-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems

Answer 2

当您划分数组时，您会找到

mid

索引。此时您有两个带有

mid

索引的部分。由于数组已排序，因此您可以将搜索元素与

mid

索引值进行比较。

如果搜索值小于

mid

索引值，则知道它在左侧，否则它在右侧。

现在，您对左半部分（索引 0 到中 - 1）或右半部分（索引中 +1 到结束）重复上述步骤（分为两部分，中间索引等）。如果搜索值与

mid

索引值相同，则找到元素并停止处理。

这个划分和比较过程持续进行，直到找到搜索元素或左右索引（最初为0和长度-1）重叠。这就是为什么会出现这种情况

left <= right

。

Answer 3

使用左<= right when you are changing the mid index in the loop

 mid = right -1
 mid = left +1

使用左< right when you are assigning the left and right directly to mid

right = mid
left = mid+1