by Minghua Tong

Binary Search的临界点分析

Binary Search说来容易，但容易出错，原因在于临界点选择。而需要考虑临界点的位置竟然有3处之多，且彼此联系。

首先，有两个原则：

  1. The target cannot be ruled out.
  2. The search space decreases over time.

最基本的Binary Search:

public class Solution {
  public int binarySearch(int[] array, int target) {
    if (array == null || array.length == 0) {
      return -1;
    }

    int left = 0, right = array.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (array[mid] == target) {
        return mid;
      } else if (array[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1;
  }
}

Critical Point 1: loop终止条件

while (left <= right)

跳出loop时，left > right。通常用在target是一个确定值，而不是一个不确定的概念（比如最接近某值）时。所谓确定，就是说loop中找到符合条件的元素时就可以直接return。loop结束时就说明target没找到，因此不需要post processing。

while (left < right)

结束时left == right。如在First Occurrence或者Last Occurrence，相对于固定的target，这是一个不确定的条件。当找到符合条件的element时，你无法判断它是不是『最』符合条件的，因此还要将范围继续缩小，直到只剩一个元素。即使只剩一个元素，它依然有可能是不符合条件的，因此还要post processing检查是否满足条件。当然post processing相对容易，只检查left或者right一个即可。

while (left < right - 1)

结束时left == right – 1。意思是说loop在search range剩下2个元素时结束。和上面一样，『最』符合条件的如果有就在这2个里面。一般是要做post processing的，需要根据题目以及loop中left，right如何更新来检查left或者right中的某一个，或者两个都检查（顺序很重要），或者两个比较。
获得的好处是，避免了dead loop！因为当right – left >= 2时，mid既不是left也不是right，能保证search range的缩小。

Critical Point 2: mid的计算方法

mid = left + (right - left) / 2;
mid = left + (right - left + 1) / 2;

当search range剩下2个元素时（如果此时依然满足loop条件），第1行会导致mid = left，第2行会导致mid = right，然后进入dead loop。如何选择要与left和right的更新方式联合考虑。

Critical Point 3: mid元素的比较与left/right的更新

if (array[mid] == target) {
    // ...
} else if (array[mid] < target) {
    // ...
} else {
    // ...
}

无外乎就三种情况，相等，小于和大于，可以先分开写，最后再整合。

left = mid;
left = mid + 1;
right = mid;
right = mid - 1;

加不加一，真不是个问题。就把住原则：The target cannot be ruled out.

结论：

总之left/right的开闭，mid的计算以及loop的条件，三个因素互相牵制，我认为下面的搭配可以最大限度的优化代码。（loop结束时left与right的范围越大，post processing越复杂，loop条件尽量选择结束时left和right的范围小的 ）

left = mid + 1, right = mid - 1
两边都选开区间的话，mid算法不重要，不管哪种循环条件都可以保证search range的缩小
可能的话选择while (left <= right)
不需要post processing

left = mid, right = mid
两边都选闭区间的话，mid算法不重要，但loop条件最好选择while (left < right - 1)，保证了search range的缩小
post processing会比较麻烦

left = mid，right = mid - 1
最好与mid = left + (right - left + 1) / 2一起使用
搭配while (left < right)
计算出的mid不会等于left，于是保证了search range的缩小
post processing只需检查left/right (left == right)

left = mid + 1，right = mid
最好与mid = left + (right - left) / 2一起使用
搭配while (left < right)
计算出的mid不会等于right，于是保证了search range的缩小
post processing只需检查left/right (left == right)

再总结，判断left/right的开闭，也有迹可循：
找到任一满足条件的就return的：左右都开left = mid + 1, right = mid - 1
需找满足条件的最左边的：左开右闭——left = mid + 1，right = mid
需找满足条件的最右边的：左闭右开——left = mid，right = mid - 1
其他：左右都闭——left = mid, right = mid

最后，Binary Search的一般解题思路：

  1. 讨论如何处理满足条件的mid（直接返回/找最左/找最右/其他）
  2. 推倒出left/right的开闭
  3. 搭配loop条件与mid算法
  4. post processing

验证：

Classical Binary Search:
1. -> 找到立刻return
2. -> left = mid + 1, right = mid - 1
3. -> while (left <= right)
3. -> left = left + (right - left) / 2
4. -> 无需post processing

Closest in Sorted Array:
1. -> 不能立刻return，既不是找最左边也不是找最右边
2. -> left = mid, right = mid
3. -> while (left < right - 1)
3. -> left = left + (right - left) / 2
4. -> 比较left和right，选closest

First Occurrence:
1. -> 需找满足条件的最左边的
2. -> left = mid + 1，right = mid
3. -> while (left < right)
3. -> mid = left + (right - left) / 2
4. -> check left or right

Last Occurrence:
1. -> 需找满足条件的最右边的
2. -> left = mid，right = mid - 1
3. -> while (left < right)
3. -> mid = left + (right - left + 1) / 2
4. -> check left or right

Search In Unknown Sized Sorted Array
Sub-problem 0: Find An Index Out of The Upper Bound

Sub-problem 1: Find The Upper Bound — the last valid index
1. -> 需找满足条件的最右边的
2. -> left = mid, right = mid – 1
3. -> while (left < right)
3. -> mid = left + (right - left + 1) / 2
4. -> check left or right

Sub-problem 2: Perform A Classical Binary Search in 0 and The Upper Bound

Leave a comment