Binary Search

This page provides links to solutions that use the binary search technique.

Overview

Binary search is an efficient algorithm used to search for a specific element in a sorted array or list. It works by repeatedly dividing the search interval in half.

Let's say we want to find index of $1$ in the array below:

$$[1, 1, 1, 1, 1, 1]$$

There are $3$ possibilities as below:

Finding Any Index

For finding any index we use classic binary search algorithm as below without any modification.

Java

public int binarySearch(int[] arr, int element) {
  int lo = 0;
  int hi = arr.length;
  while(lo < hi) {
    int mid = (lo + hi) / 2;
    // search on the left side
    if(element < arr[mid]) hi = mid - 1;
    // search on the right side
    else if(element > arr[mid]) lo = mid + 1;
    // element found
    else return mid;
  }
  // if not found return -1 as an index
  return -1;
}

Finding Leftmost Index

To find the leftmost index, we make one modification to the classic binary search algorithm. Whenever we find the element we are looking for, instead of returning the index immediately, we continue the search on the left side of that index, keeping the current index within the search space.

Java

public int binarySearch(int[] arr, int element) {
  int lo = 0;
  int hi = arr.length;
  while(lo < hi) {
    int mid = (lo + hi) / 2;
    // search on right side
    if(element > arr[mid]) lo = mid + 1;
    else {
      // continue searching on the left side 
      // to find the leftmost index that contains the same value.
      hi = mid;
    }
  }
  return lo;
}

Finding Rightmost Index

To find the rightmost index, we make two modification to the classic binary search algorithm.

• Whenever we find the element we are looking for, instead of returning the index immediately, we continue the search on the right side of that index, keeping the current index within the search space.
• We use below formula for calculating mid value.

$$\frac{\text{(lo + hi + 1)}}{2}$$

Let's understand this with given input array $[1, 1, 1, 1, 1, 1]$ and search element $1$. Also let's assume we don't use above formula for calculating mid and instead use classic formula.

Initially, the mid will be at index $3$, as shown in the snapshot below.

Since the element at mid is the one we are looking for, we assign mid to lo, keeping that index within the search space.

Recalculating mid gives us a new mid value of $4$.

Again, mid already contains the element we are looking for, we assign mid to lo, keeping that index within the search space.

Recalculating mid gives us a new mid value of $5$.

Once again, mid already contains the element we are looking for, we assign mid to lo, keeping that index within the search space.

Recalculating mid gives us a new mid value of $5$, and we would be stuck in loop with lo $= 5$, mid $=5$ and hi $=6$ indefinitely. To avoid this, we use modify classic formula for calculating mid and add $1$ to numerator.

Java

public int binarySearch(int[] arr, int element) {
  int lo = 0;
  int hi = arr.length;
  while(lo < hi) {
    // mid calculation is modified to avoid indefinate loop.
    int mid = (lo + hi + 1) / 2;
    // search on right side
    if(element < arr[mid]) hi = mid - 1;
    else {
      // continue searching on the right side 
      // to find the rightmost index that contains the same value.
      lo = mid;
    }
  }
  return lo;
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

Time complexity of binary search is:

$$\text{O(log N)}$$

Space Complexity

Binary search requires constant space.

$$\text{O(1)}$$

How to Spot These Problems

You can identify binary search problems if the problem requires you to:

• Search for a specific element or target value in a sorted array or list.
• Determine the maximum or minimum value that satisfies certain conditions.
• Find the first or last occurrence of a particular element in a sorted array.
• Split an array or range into subarrays or subranges and solve subproblems within these divisions.

Leetcode Problem Set

# ▲	Solution
410	Split Array Largest Sum
1011	Capacity To Ship Packages Within D Days
1231	Divide Chocolate
1891	Cutting Ribbons
2591	Distribute Money to Maximum Children
2064	Minimized Maximum of Products Distributed to Any Store

Total Solved: 6