在二分搜索中混淆何时使用 left < right ；左 <= 右 ; 还有更多

Question

我很难理解何时使用：

while (left < right ) {
}

vs 何时使用：

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来计算 mid，但使用(lo+hi)/2可能会导致溢出。现在混乱的部分：

while (lo <= hi)如果我们从循环内部返回匹配，则使用。我们while (lo < hi)想先退出循环，然后使用loor的结果hi来返回匹配项。

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