The Ultimate Binary Search Guide: Exploring Different Templates for Success

In this article, we will explore various templates of binary search and demonstrate their practical application through solving select LeetCode problems. We have three templates of binary search:

1. Exact Matching
2. Upper Bound
3. Lower Bound

We will Explain The Templates Using One Example

Figure 1: Binary Search Example

1. Exact Matching:

This is the most basic variant of binary search as we are searching for the exact match for a certain target

let's say we want to find the number 3

1- we will set lo/hi and calculate the mid-position

int lo = 0;
int hi = nums.length - 1;
int mid = lo + (hi - lo)/2;

Figure 2: Binary Search Exact Match

2- after checking our conditions
- If target > mid value we will set lo to m+1
- If target < mid value we will set hi to m-1
- If target == mid value we found our target and we can return the index of that element

if(nums[mid] == target)
  return target;
else if(nums[mid] > target)
  hi = mid - 1;
else
  lo = mid + 1;

3- our target < mid value so we will set hi

Figure 2.1: Binary Search Exact Match

4- We will continue to perform the same operation until either the value of 'lo' becomes greater than 'hi', or we find our target.

Figure 2.2: Binary Search Exact Match

5- we found our target so we can return.

But what happens if we do not find our target?

That is our escape condition if lo > hi, it means we didn’t find our target and we can escape our iteration or recursive calls.

Full code version

Iterative:

public int bs(int[] nums, int target) {
  int lo = 0;
  int hi = nums.length -1;
  int m;
  while(lo <= hi) {
    m = lo + (hi - lo)/2;
    
    if(nums[m] == target)
        return m;
    else if (nums[m] > target)
        hi = m - 1;
    else
      lo = m + 1;
  }

  return -1;
}

Recursive:

public int bs(int[] nums, int target) {
  return bsh(nums, target, 0, nums.length - 1);
}

public int bsh(int[] nums, int target, int lo, int hi){
  if(lo > hi)
    return -1;
  int mid = lo + (hi - lo)/2;
  if(nums[mid] == target)
     return mid;
  if(nums[mid] > target)
    return bsh(nums, target, lo, mid-1);
  if(nums[mid] < target)
    return bsh(nums, target, mid+1, hi);
  return -1;

}

Note that we do not need any Post-processing keep that in mind for now

2. Upper Bound:

Back to our example

Figure 3: Binary Search Example

Let's say we want to get the last occurrence of 7 which will be the index 5

we can do exact matching like the last template as following

Figure 3.1: Binary Search Finding mid value

The mid value equals our target so we will return index 3
after that, we can do linear scanning till we reach the last position of 7.

Figure 3.2: Linear scanning to get the last position of the target

The problem with that approach is the time complexity is O(N)

Can we do better?

Yes as you guessed we can use binary search to get the upper bound with a simple modification to the binary search algorithm.

Figure 3.3: Binary Search Upper Bound

The only modification we will make is to the conditions we have

• If target ≥ mid value we will set lo to m+1 “We merged the equality with moving the lo pointer”
• If target < mid value we will set hi to m “We set hi to m”
• Also, our escape condition will be lo ≥ hi

the target is more or equal to the mid-value so we update the “lo” value

Figure 3.4: Binary Search Upper Bound

we do the same steps

Figure 3.5: Binary Search Upper Bound

Note that in the upper Bound version, we must post-process after the binary search algorithm.

Full Code:

public int bs(int[] nums, int target) {
  int lo = 0;
  int hi = nums.length;
  int m;

  while(lo < hi){
    m = lo + (hi - lo)/2;
    if(nums[m] <= target)
        lo = m+1;
    else
        hi = m;
  }

  // NOTE THE POST PROCESSING WE NEED TO DO 
  if(lo > 0 && nums[lo-1] == target)
      return lo-1;
  else
    return -1;

}

3. Lower Bound:

Using The same example as last time

Figure 4: Binary Search Example

we want to find the first occurrence of the number 7

we will calculate mid as usual and get our mid value.

Figure 4.1: Binary Search Finding mid value

We will modify our conditions as following

• If target > mid value we will set lo to m+1 “We set lo to m”
• If target ≤ mid value we will set hi to m “We merged the equality with moving the hi pointer”
• Also, our escape condition will be lo ≥ hi

the target is less or equal to the mid-value so we update the “hi” value

Figure 4.2: Binary Search Lower bound

we do the same steps

Figure 4.3: Binary Search Lower bound

Figure 4.4: Binary Search Lower bound

Note that we must post-process after the binary search algorithm in the Lower Bound version too.

public int bs(int[] nums, int target) {
  int lo = 0;
  int hi = nums.length;
  int m;

  while(lo < mid){ 
    m = lo + (hi - lo)/2;
    if(nums[m] < target)
        lo = m+1;
    else
        hi = m;
  }

  // NOTE THE POST PROCESSING WE NEED TO DO
  if(lo < nums.length && nums[lo] == target)
      return lo;
  else
      return -1;
}

Congratulations now we know the different templates of the binary search.

Figure 5: Yes meme

From achieving precision with Exact Matching to optimizing with the Upper Bound and finesse in the Lower Bound, these templates empower diverse problem-solving. With these tools, you are set to navigate the binary search landscape with confidence.

Stay tuned for the next article, where we will step-by-step unravel a LeetCode problem. An exciting coding journey awaits!