Fully Understand Binary Search

Posted on | Post modified:
Words count in article: 427

Here is a blog particularly for the Binary Search implementation. Though it is a very fundamental algorithm, it stll lays a foundation for a lot of other problems. And it is necessary to dive deep for it.

First let’s talk about the traditional implementation version of the binary search: 

1
2
3
4
5
6
7
8
9
bool search(int x[], int n, int k) {
    int l = 0, r = n-1;
    while (l <= r) {
        int m = (l+r)/2;
        if (x[m] == k) return true;
        if (x[m] < k) l = m+1; else r = m-1;
    }
    return false;
}

Observation:

  1. The scope of the initial boundary is [0, n - 1], which is the entire available elements set. The reason why we choose this could be explained by the update strategy for the boundary variables l and r. Since they are updated as mid - 1 or mid + 1, they could be set to any elements inside the entire scope. So we should not make the boundary exceed the valid index set.
  2. The update strategy for the l and r is reasonable when we think about a decision tree. Take left boundary l for example, if the current midpoint mid could not meet the predefined requirement, then all the elements on the leftside of mid, while including the midpoint, should be excluded from the choice scope. And we can do this by assign mid + 1 to l.
  3. According to the update strategy, it is possible that we will reach the situation when l equals to r. Thus, the while clause should be l <= r, which includes the equality situation.
  4. It is always helpful to consider the situation when the binary search hit the end, so that we can easily find the correct boundary and update strategy. For example, in leetcode [35], consider what will happen in the final step where l == r - 1, and there’s no element equal to target. According to the previous updating strategy, l will be set to mid + 1 and the binary search is finished. So the final output of the algorithm will be at the first value that is equal or bigger to the target.
  5. The template could easily support the operations like finding equality in list and find the first element that is not satisfied the mentioned property [in this case, element in l will be the first element that is not satisfied the property].
  6. https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/
0%