An opinionated guide to binary search (comprehensive resource with a bulletproof template)
darkalarm
24069
Binary SearchCareerstudy guide

An opinionated guide to binary search

A comprehensive and updated guide to binary search. Includes a template that works in every case.
A rich problem set and solutions using the suggested methodology. Includes pictures for easy understanding.
Beginner friendly.

Table of Contents

Introduction

If you are someone who has seen multiple ways of implementing binary search, and have been getting confused on which one to use, when to use, this guide should be for you. Best, I'm going to give you one template that works in absolutely all cases. Which means, there is going to be no confusion. I would suggest to look at this with an open mind and try it once before making up your mind against this approach.

Binary search divides the search space into half until we reach the result. As a result the time performance of binary search (log n) is considerably better than linear search (n). This means where linear search will take 10^6 steps, binary search will do it in only 17 steps.

Binary search usually works for sorted arrays. But don't make the mistake of assuming it works only on sorted arrays. A bigger question to ask is if the search space can be perceived as or converted into a monotonically increasing / decreasing function. Typically, you'll be asked to return a minimum value that satisfies a given condition or the maximum value that satisfies a given condition. We'll learn it as we go through the examples below.

Template

I try to convert each binary search related problem in either of the two formats - minimization problem (minimize x such that condition(x) is true) or maximization problem (maximize x such that condition(x) is true). In both the cases we construct the condition(x) such that it is true for our answer.


// minimize x such that condition(x) is true
function binarySearch(arr) {
  // decide what is the search space
  // hi should be able to take all possible values in the search space
  // lo points to an invalid value (the negative case of the if condition)
  let lo = -1, hi = arr.length;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (condition(arr, mid)) {
      hi = mid
    } else {
      lo = mid;
    }
  }

  // in minimization template, hi contains the return index
  return hi;
}

// maximize x such that condition(x) is true
function binarySearch(arr) {
  // decide what is the search space
  // lo should be able to take all possible values in that search space
  // hi points to an invalid value (the negative case of the if condition)
  let lo = -1, hi = arr.length;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (condition(arr, mid)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }

  // in maximization template, lo contains the return index
  return lo;
}

function condition(arr, idx) {
  // some condition on arr[idx]
  // return true or false
  return true;
}

Example

Minimization - Find first occurrance of an element in a sorted array with duplicates.
Maximization - Find last occurrance of an element in a sorted array with duplicates.

Notes

If you look at both the templates carefully. We can make the following observations:

In minimization template, hi contains the final answer.
In maximization template, lo contains the final answer.

In each of the template, the variable that contains the final answer (hi for minimization / lo for maximization), should be able to take all possible values in the search space. In other words, one variable always holds the answer (or the valid value) and the other variable holds the invalid value.

When we exit from while loop, lo and hi are adjacent to each other. (lo + 1 < hi) will not be true when lo + 1 === hi.

The while loop condition guarantees that you always will have at least three values in the search space (lo, mid, hi). Although, the way we initialize the values for lo and hi, only one of them holds a valid value at any point in time.

Comparing with other template styles

There are other binary search templates which use (lo <= hi) or (lo < hi) in the while condition. I don't like it, because in one template you end up deciding whether to move lo to mid + 1 or hi to mid - 1. If you commit a mistake, you might endup in an infinite loop. In the other template, you have to remember whether lo goes to mid + 1 or hi goes to mid + 1. Something that keeps me away from making these critical decisions will be better. This is why it is an opinionated guide.

In this template, the condition is simple and the decision is simple. The decision is to either assign mid to lo or hi, depending on maximization or minimization. At the end, lo and hi are adjacent to each other, we don't go into an infinite loop as well.

The most important part of the template is the condition function. We make this function in such a way that it gives us either of the following two answers:

(this is minimization template - find the first true)
[false, false, false, true true, true, true]

OR

(this is maximization template - find the last true)
[true, true, true, false, false, false, false]

comparison between minimization template and maximization template for binary search

Process

I like to think of Binary Search based problems as a three steps process.

  1. Decide the search space.(lo and hi will be initialized accordingly)
  2. Find a monotonic function which increases or decreases with the input. It can take one of the two forms (false followed by true or true followed by false)
  3. decide whether lo holds the answer or hi holds the answer. If it is a minimization problem (FFFFTTT) then hi holds the answer. If it is a maximization problem (TTTFFFF) then lo holds the answer.

Usually, coming up with a monotonic function is the most crucial steps. We'll take enough examples to cement your understanding about the process.

image

Example problems

If nothing made sense until this point, don't worry. The current section is where you'll actually develop the understanding and intuition for a binary search based problem. Let's dive in!

278. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out which one is the first bad one, which causes all the following versions to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution

Let's decide a few things / make some observations before jumpting into the solution:

  1. Our search space is monotonically increasing. If a version fails, then all versions after it also fail.
  2. Any version starting from 1 to n could be bad. This means our search space is [1, n] (inclusive).
  3. We want to find the first bad version. If the condition inside the while loop is going to be isBadVersion(version), then we can see that we want to find the minimum version, such that isBadVersion(version) is true. This is the minimization template.
  4. In minimization template, hi gives the final answer. So we initialize lo to a value that is going to be invalid. We initialize hi to a value that is going to be maximum in the search space.
  5. lo = 0, hi = n;

type: minimization problem
range: lo -> invalid (0), hi -> valid (1 to n)
initialize: lo to 0, hi to n.
condition: f(x) = isBadVersion(x)


function firstBadVersion(n) {
  let lo = 0, hi = n;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isBadVersion(mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }

  return hi;
}

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Solution

It is a minimization problem. The target can be placed anywhere between 0 index and arr.length (after the last element).
We want to find first such position where the condition the number is greater or equal to target is true.

type: minimization problem
range: lo -> invalid (-1), hi -> valid (0 to nums.length)
initialize: lo to -1, hi to nums.length
condition: f(x) = x >= target


var searchInsert = function(nums, target) {
  let lo = -1, hi = nums.length;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isGreaterOrEqual(nums[mid], target)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  // hi contains the answer
  return hi;
};

function isGreaterOrEqual(num, target) {
  return num >= target;
}

Note: read more about this question in the discussion section below.

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

The array can contain duplicates, or it is possible that the element is not present in the array.

Solution

Find first occurrance of the element.

type: minimization problem
range: lo -> invalid (-1), hi -> valid (0 - nums.length)
initialize: lo to -1, hi to nums.length. If the hi remains unchanged till the end, we know that the element doesn't exist and we can return -1, otherwise we return hi.
condition: f(x) = x >= target


function findFirstOccurrance(nums, target) {
  let lo = -1, hi = nums.length;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isGreaterOrEqual(nums[mid], target)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  if (hi === nums.length || nums[hi] !== target) {
    return -1;
  }
  return hi;
}
Find the last occurrance of the element.

type: maximization problem
range: lo -> valid (-1 to nums.length - 1), hi -> invalid (nums.length)
initialize lo to -1, hi to nums.length
if the lo remains unchanged till the end, we know that the element doesn't exist
we can return lo (because when it is unchanged, it is already -1)
condition: f(x) = x <= target


function findLastOccurrance(nums, target) {
  let lo = -1, hi = nums.length;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isSmallerOrEqual(nums[mid], target)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  if (lo === -1 || nums[lo] !== target) {
    return -1;
  }
  return lo;
}
Merge

Now that we have the first and last occurrances both, we can use the following code to find the range:


function findRange(nums, target) {
  let first = findFirstOccurrance(nums, target);
  let last = findLastOccurrance(nums, target);
  return [first, last];
}

Isn't that simple?

1150. Check If a Number Is Majority Element in a Sorted Array

Given an array nums sorted in non-decreasing order, there is a special number in the array nums, which is unique in the array and occurs at least twice. Find the number if it exists in the array.

Solution

Because the array is sorted, a majority element will occur multiple times at adjacent locations to each other. If we can find the index of the first occurrance of the target, and the last occurrance of the target. We can say that the element is a majority element if the distance between the first and last occurrance is greater than n / 2.

In another words, we can use findRange function above on the target element. If the return range is greater than n / 2, then the element is a majority element.


function findMajorityElement(nums, target) {
  let range = findRange(nums, target)
  if (range[0] === -1) {
    return -1;
  }
  let rangeLength = range[1] + 1 - range[0];
  return (rangeLength > nums / 2);
}

744. Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Solution

type: minimization problem
range: lo -> invalid (-1), hi -> valid (0 - letters.length)
initialize: lo to -1, hi to letters.length
if the hi remains unchanged till the end, we wrap it around and answer 0.
condition: f(x) = x > target


function nextGreatestLetter(letters, target) {
  let lo = -1, hi = letters.length;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isGreater(letters[mid], target)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi === letters.length ? letters[0] : letters[hi];
}

function isGreater(letter, target) {
  return letter > target;
}

441. Arranging Coins

You have n coins that you want to form in a staircase shape. The staircase consists of n levels, and the i-th level has i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of full staircase rows that can be formed.

Solution

Every level has one more than the previous level. If there are 5 full rows, it'll look something like this
[1, 2, 3, 4, 5] - first row has 1 coin, second row has 2 coins, third row has 3 coins, fourth row has 4 coins, and fifth row has 5 coins.

Let's say there are k complete, and 0 incomplete rows. Then the total number of coins would be k * (k + 1) / 2.

According to the problem, there could be at most 1 incomplete row at the end. We already know that the toal number of coins is n.

So, the condition that should hold true is:

f(k) = k * (k + 1) / 2 <= n and we want to maximize k. It is clear that it is a maximization problem. So, lo will hold the valid value and hi will hold the invalid value.

Let's summarize our understanding here.

type: maximization
range: lo -> valid (1), hi -> invalid (n + 1). the number of rows will always be smaller than the number of coins + 1.
initialize: lo to 1, hi to n + 1
condition: f(k) = k * (k + 1) / 2 <= n


function arrangeCoins(n) {
  let lo = 1, hi = n + 1;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (coinCountInRows(mid) <= n) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  return lo;
}

function coinCountInRows(rowCount) {
  return rowCount * (rowCount + 1) / 2;
}

153. Find Minimum in Rotated Sorted Array

Suppose an array of unique integers sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find index of the minimum element.

Solution

If the array was not rotated, we could simply return the first element of the array. In this case the array has been rotated, which means it is sorted until the pivot. And then it is sorted after the pivot. It is not sorted at the pivot.

We want to find a monotonic function here. This function will map the array elements to a series of boolean values. These values will be a series of false values followed by true values for each of the indices.

Turns out, we can. For a rotated sorted array, we can compare each element with the last element of the array. If the current value is less than or equal to the last value, then we know that we are on the right side of the pivot. If the current value is greater than the last value, then we know that we are on the left side of the pivot.

Example:
arr = [4,5,6,7,0,1,2]
isOnRight = [false, false, false, false, true, true, true]

Here, the pivot is between 7 and 0. This means, 0, 1, 2 are on the right side of the pivot, and 4, 5, 6, 7 are on the left side of the pivot. So, isOnRight function will return true for 0, 1, 2. The first element is 0, which is also our answer.

The minimum value is the first value on the right side of the pivot.

type: minimization problem
range: lo -> invalid (-1), hi -> valid (0 - nums.length - 1)
initialize: lo to -1, hi to nums.length - 1
condition: f(x) = x <= nums[nums.length - 1]

Note - Read interesting discussion around this question in the comments below. This should clarify some confusions.


function findMin(nums) {
  let lo = -1, hi = nums.length - 1;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isOnRight(nums, mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
}

function isOnRight(nums, index) {
  return nums[index] <= nums[nums.length - 1];
}

Exercise: In this case all the elements were unique. What would happen if duplicates are allowed in the sorted rotated array?

33. Search in Rotated Sorted Array

In the previous question, you found the minimum number in a rotated sorted array. In this one, you need to find a target value in this array.

Solution

For solving this question, let's find the index of the minimum element first. Once we know the index, we can either search for the element on the left side of the pivot or the right side of the pivot. This would be decided based on whether the target is smaller than the right most element or not.


function searchRotatedSortedArr(arr, target) {
  let minIndex = findMin(arr);
  if (isOnRight(arr, target)) {
    return binarySearch(arr, target, minIndex, arr.length - 1);
  } else {
    return binarySearch(arr, target, 0, minIndex - 1);
  }
}

function isOnRight(arr, target) {
  return target <= arr[arr.length - 1];
}

// type: minimization
// scale: `lo` -> invalid (left - 1), `hi` -> valid (left - right) (inclusive)
// initialize: `lo` to `left - 1`, `hi` to `right`
// condtion: `f(x) = x >= target`

function binarySearch(arr, target, left, right) {
  let lo = left - 1, hi = right;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isGreaterOrEqual(arr[mid], target)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return arr[hi] === target ? hi : -1;
}

function isGreaterOrEqual(num, target) {
  return num >= target;
}

162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given a 0-indexed array where A[i] ≠ A[i+1], find a peak element and return its index. If the array contains multiple peaks, return the index to any one of the peaks.

Solution

The peak element could be any from 0 to n - 1. The monotonic function will be whether the current value is greater than the next value or not. We are interested in finding the first such index which returns true for this function.

type: minimization problem
range: lo -> invalid (-1), hi -> valid (0 - nums.length - 1)
initialize: lo to -1, hi to nums.length - 1
condition: f(x) = nums[x] > nums[x + 1]


function findPeakElement(nums) {
  let lo = -1, hi = nums.length - 1;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isGreater(nums, mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
}

function isGreater(nums, index) {
  // if it is the last index of the array, then the condition holds true
  if (index === nums.length - 1) {
    return true;
  }
  return nums[index] > nums[index + 1];
}

Note: The problem could be converted into a maximization problem if we flip the condition to nums[index] > nums[index - 1].
In this case lo will always remaing valid (from 0 to n - 1) and hi will always be invalid (initialized to n). This is possible for most other problems as well. I would suggest giving it a thought when creating the monotonic function, and decide it for yourself.

845. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Solution

You can notice that the array is not sorted in this question. But we can still apply binary search to find the answer. Why? Because we can convert the search space into a series of TTTFFF or FFFTTTT values.

Let's see what is the search space here. We want to return the speed k at which Koko can eat all the bananas in h hours. The search space is the range of k values that Koko can choose. At the minimum, it could be 1 (at 0, Koko won't eat anything at all). The upper bound is the maximum of all piles. Because it is given in the question that h is greater than the number of piles. So, if the speed is the maximum of all piles, Koko can surely eat bananas in h hours.

So, we can say our search space is [1, max(piles)]. We want to find the minimum value in this search space, in other words, this is a minimization problem. Our monotonic function will be canFinishInHHours(piles, k). This would result in a series of FFFFTTTT values. We need to find the minimum value in the search space that return true.

type: minimization
range: lo -> invalid (0), hi -> valid (1 to max(piles))
initialize: lo to 0, hi to max(piles)
condition: f(x) = canFinishInHHours(piles, x)


function minEatingSpeed = function(piles, h) {
  let lo = 0, hi = Math.max(...piles);
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (canFinishInHHours(piles, mid, h)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
}

function canFinishInHHours(piles, speed, maxHours) {
  let time = 0;
  for (let i = 0; i < piles.length; i++) {
    // time it takes to eat each of the pile
    // if the number is less than the speed,
    // then Koko can't move to the next pile
    // before the current hour is compleleted
    time += Math.ceil(piles[i] / speed);
    if (time > maxHours) {
      return false;
    }
  }
  return true;
}

540. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Solution

If all the elements had duplicates, what property would they have?
Example: [1, 1, 3, 3, 5, 5, 7, 7, 9, 9];
Elements at the index [0, 2, 4, ..., n - 2] would all have a duplicate element on the right.
Elements at the index [1, 3, 5, ..., n - 1] would all have a duplicate element on the left.

Now if I insert 6 in the array in sorted order. This is going to disturb the property above.
After insertion: [1, 1, 3, 3, 5, 5, 6, 7, 7, 9, 9];
Because 6 is inserted at index 6, the property still holds true until the index 5;

Let's build it as a minimization problem on the inverse of the property discussed above. For all the values on the right side of the index 5:

  • if index is even, there is no duplicate element on the right
  • if index is odd, there is no duplicate element on the left

We want to find the minimum index for which the above property holds true.

type: minimization
range: lo -> invalid (-1), hi -> valid (1 to nums.length - 1)
initialize: lo to -1, hi to nums.length - 1
condition: f(x) = isOnRightSide(x)


function singleNonDuplicate(nums) {
  let lo = -1, hi = nums.length - 1;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (isOnRightSide(nums, mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
}

function isOnRightSide(nums, idx) {
  if (idx % 2 === 0) {
    return nums[idx] !== nums[idx + 1];
  } else {
    return nums[idx] !== nums[idx - 1];
  }
}

1891. Cutting Ribbons

You are given an integer array ribbons. Each element represents the length of a ribbon. You are also given an integer k. You need to cut the ribbon into exactly k pieces. You may cut any of the ribbons into any number of segments of positive integer length, or perform no cuts at all.

Your goal is to obtain k ribbons of all the same positive integer lengths. You are allowed to throw away any excess ribbon as a result of cutting.

Return the maximum possible positive integer length that you can obtain k ribbons of. Or 0 if you cannot obtain k ribbons of the same length.

Solution

type: maximization
range: lo -> valid (1 to max(ribbons)), hi -> invalid (max(ribbons) + 1)
initialize: lo to 0, hi to max(ribbons) + 1
condition: f(x) = (count of ribbons of size x) >= k

if x is lower, count will be higher, and when x is higher, count will be lower
so as we move from left to right on the values of x, our fuction would move from true to false values
we want to find the maximum x such that our function (condition) holds true
if we can't obtain k ribbons in such a way, lo would remain unchanged at 0. which will be our answer.f


function maxLength(ribbons, k) {
  let lo = 0, hi = Math.max(...ribbons) + 1;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (canObtainRibbonCount(ribbons, mid, k)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  return lo;
};

function canObtainRibbonCount(ribbons, length, count) {
  let currentCount = 0;
  for (let i = 0; i < ribbons.length; i++) {
    currentCount += Math.floor(ribbons[i] / length);
    if (currentCount >= count) {
      return true;
    }
  }
  return false;
}

1060. Missing Element in Sorted Array

Given an integer array nums which is sorted in ascending order and all of its elements are unique. Given an integer k, return the kth missing number starting from the leftmost number of the array.

Solution

There are two tricky parts of this question. 1. deciding the search space 2. deciding the monotonic function which works on the search space.

Deciding monotonic function

For each of the array indexes we can find the number of missing elements in the array in O(1). The number of missing elements at each index could either be less than k, or greater than or equal to k. Now this is a monotonic function of type TTTTTFFF. If we can find the last index lo where the number of missing elements is less k, then we can find the kth missing element using the following formula:

kthMissing = nums[lo] + k - countOfMissingElementsAt(lo)

countOfMissingElements is the monotonic function here. It is defined as:

  // difference in values at current index and the first index -
  // difference in the current index and first index
  countOfMissingElements(i) = nums[i] - nums[0] - i

Deciding search space

We know that at index 0 there is no missing number. At index n - 1 we can calculate the count of missing numbers - say it is x. If we initialize lo at 0 and hi at nums.length, then we need to find the maximum lo such that the number of missing elements is less than k.

type: maximization
range: lo -> valid (0 to nums.length - 1), hi -> invalid (nums.length)
initialize: lo to 0, hi to nums.length
condition: f(x) = countOfMissingElementsAt(x) < k

Code


function missingElement(nums, k) {
  let lo = 0, hi = nums.length;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    // we find the maximum value of lo, such that missingAt(nums, lo) <= k
    if (missingAt(nums, mid) < k) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  
  return nums[lo] + k - missingAt(nums, lo);
};

function missingAt(nums, idx) {
  return nums[idx] - nums[0] - idx;
}

1102. Path With Maximum Minimum Value

Given an m x n integer grid grid. Return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1). The path can move in 4 cardinal directions. The score of a path is the minimum value in the path.

Solution

This is one of those questions where getting a binary search intuition might be difficult. There is no sorted array in sight (which usually gives a hint on using binary search). If we look carefully, the search space is visible though.

This is also one of those questions where the main binary search logic is very simple, but the monotonic function condition is a bit involved.

Because the score of a path in the minimum value of the path, it has to be lower than or equal to the minimum of the value at the starting point (top left) or the ending point (bottom right). This can act as the upper bound for our problem. We can assume the lower bound to be 0.

We want to find a path with the maximum score. This maximum score will be the answer. Let's take a value x between the upper and the lower bound, and check if we can reach the destination with a score >= x. This becomes our monotonic function that we put in the if condition.

This is essentially a maximization problem, where lo will atain the valid values in the search space (when the condtion is true) and hi will attain the invalid value.

type: maximization
range: lo -> valid (0 to min(grid[0][0], grid[m - 1][n - 1])), hi -> invalid (min(grid[0][0], grid[m - 1][n - 1]) + 1)
initialize: lo to 0, hi to min(grid[0][0], grid[m - 1][n - 1]) + 1
condition: f(x) = pathExistsWithScore(x)

We can use BFS to find out if a path exists with a given score. If we find a node with a value < x we discard it. If we endup reaching the destination, we know that it is a valid path.


function minimumPath(grid) {
  let lo = 0, hi = Math.min(grid[0][0], grid[grid.length - 1][grid[0].length -1]) + 1;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (pathExists(grid, mid)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  
  return lo;
};

function pathExists(grid, score) {
  let queue = [[0, 0]];
  let seen = new Set(`0-0`);
  
  while (queue.length) {
    let [row, col] = queue.shift();
    if (row === grid.length - 1 && col === grid[0].length - 1) {
      return true;
    }
    // explore its neighbor if the value is greater than or
    // equal to score
    for (let [deltaX, deltaY] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {
      let newRow = row + deltaX;
      let newCol = col + deltaY;
      if (isValid(grid, newRow, newCol) && !seen.has(`${newRow}-${newCol}`)) {
        seen.add(`${newRow}-${newCol}`);
        if (grid[newRow][newCol] >= score) {
          queue.push([newRow, newCol]);
        }
      }
    }
  }
  
  return false;
}

function isValid(grid, row, col) {
  return (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length);
}

2187. Minimum Time to Complete Trips

You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Solution

Another question where intuition wouldn't come right away. But if you have been looking at these problems for a while, you might slowlty start developing an intuition here. Let's look at different parts of the problem one by one.

Search Space - we want to find the minimum time required. At the very least it can be 1. So the lower bound is simple. Upper bound could be governed by the minimum value in time array. We can multiply this minimum value by the number of totalTrips which should give us an upper bound.

Monotonic function - at any point in time, the total number of trips completed can be calculated by adding the number of trips completed by each bus. This is a monotonic function. It returns true if the number is greater than or equal to targetTrips.

The structure will look something like this - FFFTTTTT. Our task is to find the first truth returned by this function.

Let's summarize:

type: minimization
range: lo -> 0 (invalid), hi -> 1 to min(time) * totalTrips (valid)
initialize: lo to 0, hi to min(time) * totalTrips
condition: f(x) = totalTripsCompleted(x) >= targetTrips


function minimumTime(time, totalTrips) {
  let lo = 0, hi = Math.min(...time) * totalTrips;
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (areTargetTripsCompleted(time, mid, totalTrips)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
};

function areTargetTripsCompleted(times, atTime, targetTrips) {
  let trips = 0;
  for (let time of times) {
    trips += Math.floor(atTime / time);
    if (trips >= targetTrips) {
      return true;
    }
  }
  return false;
}

378. Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where a[i][j] represents the ith row and jth column, find the kth smallest element in the matrix.

It is given that each row and column is sorted in ascending order.

Solution

It might be difficult to come up with the intuition for binary search in this question. The array is sorted, but it is not linear.
The search space - kth element is between 0 to n * n - 1 index element. So we have a vague idea of the search space, which is between the lowest value in the matrix (stored at 0, 0) and the highest value in the matrix (stored at n - 1, n - 1).

The hard part is to come up with a monotonic function that returns true for all values greater than or equal to the kth element.

For kth element, we know that there will be exactly k elements in the matrix which will be lower than or equal to the kth element.

This should give us a hint on the monotonic function. Given a number x in the range - what is the count of numbers in the matrix which are lower than or equal to x? If I can answer this question, I can come up with a monotonic function.

f(x) = countLessThanOrEqual(grid, x) >= k

For the search range of all numbers between lo and hi, this would give a pattern of FFFF..TTTT. We want to find the first T. So this is a minimization type problem.

Counting elements less than or equal to a given number in the matrix

Because the matrix is sorted in both row and column, we start at the lower left corner of the matrix. If the current number is greater than or equal to x, we add all the numbers in the current column to our count (count += rowIndex + 1), and move to the next column.
If the current number is less than x, we move to the previous row (the element directly above). Continue the same process.

Let's summarize:

type: minimization
range: lo -> grid[0][0] - 1 (invalid), hi -> grid[0][0] to grid[n - 1][n - 1] (valid)
initialize: lo to grid[0][0] - 1, hi to grid[n - 1][n - 1]
condition: f(x) = countLessOrEqualInGrid(grid, x) >= k


function kthSmallest(grid, k) {
  let lo = grid[0][0] - 1, hi = grid[grid.length - 1][grid[0].length - 1];
  
  while (lo + 1 < hi) {
    let mid = lo + Math.floor((hi - lo) / 2);
    if (countLessOrEqualInGrid(grid, mid) >= k) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
}

// monotonic function used in the if condition above
// returns the number of elements less than or equal to
// the supplied number `num` in the matrix `grid`
function countLessOrEqualInGrid(grid, num) {
  let count = 0;
  let i = grid.length - 1;
  let j = 0;
  while (i >= 0 && j < grid[0].length) {
    if (grid[i][j] <= num) {
      count += i + 1;
      j += 1;
    } else {
      i -= 1;
    }
  }
  return count;
}

Conclusion

If you have made it till this point, congratulations, you have graduated in efficiently solving problems based on Binary Search. We covered a lot of problems involving different kind of condition functions. I also showed you that binary search is not limited to only sorted arrays. It rather depends on being able to convert search space in a monotonic function.

I also gave you an opinionated binary search template. This template has worked wonderfully for me, and I haven't come across any binary search based problem where I couldn't apply this technique.

I would now suggest you to try more problems based on Binary Search technique yourself. The more problems you'll do the better your intuition will get. Trust me, a few months ago I was in the same boat, but with practice I've gotten much better. I have a fairly average problem solving aptituide, and if I can do it, you can do it as well.

To try more of binary search based problem you can go to this tag page.

p.s. If you come across a problem that you are having a hard time solving with the template shared here, please share it in the comment below and I'll try my best to give you an answer.

If you enjoyed this article you might like another article I recently wrote about solving Monotonic Stack based problems with a bulletproof template. Give it a read.

Comments (66)