binary-search - 在二分搜索中混淆何时使用 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计算中值，但使用 (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.