Fully Understand Binary Search

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.
0%