This is a note to myself and might contain bugs.

Binary Search

If you’re reading this article, chances are you already know the basics of binary search and are looking for a template you can reuse across different problems.

Most tutorials teach binary search as a way to search for an element inside a sorted array. While that’s certainly one application, the same technique can also be used to search over a range of possible answers.

The only requirement is that the search space is monotonic.

Classic Binary Search

Let’s start with the binary search everyone learns first.

function binarySearch(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

Every iteration checks the middle element.

If the target is smaller, we discard the right half.

If it’s larger, we discard the left half.

Since we eliminate half of the remaining search space every iteration, the algorithm runs in O(log n) time.

The template we’ll discuss next follows exactly the same principle. The only difference is that instead of searching for an exact value, we’re searching for the point where a condition changes.

The “First True” Pattern

The template below solves a very common class of problems:

Given a monotonic boolean condition (check()), find the smallest value for which the condition becomes true.

Notice that we are not searching for a specific value anymore.

Instead, we are searching for the boundary where the predicate changes.

Imagine evaluating check(x) for every possible value.

false false false false true true true true true
                        ^
                   this is the answer

Everything before the boundary returns false.

Everything after the boundary returns true.

The goal of binary search is to locate that transition point without checking every value individually.

Why Monotonicity Matters

The most important requirement for this template is that check() must be monotonic.

Once the condition becomes true, it should never become false again.

Good:

F F F F T T T T T

Also good:

T T T T F F F F

Bad:

F T F T T F

In the last example, binary search has no idea which half to eliminate because the pattern keeps changing.

Whenever you’re thinking about applying binary search, ask yourself one question:

If check(x) is true, can I guarantee that every larger value is also true?

If the answer is yes, this template is usually applicable.

Binary Search Template

let low = ...;
let high = ...;
let ans = -1;

while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (check(mid)) {
        ans = mid;
        high = mid - 1;
    } else {
        low = mid + 1;
    }
}

return ans;

At first glance, it looks like just a few lines of code.

In reality, every line has a purpose.

Let’s break it down.

1. low and high

let low = ...;
let high = ...;

These variables define the search space.

A common misconception is that binary search always searches an array.

It doesn’t.

Binary search searches any ordered space.

Sometimes that space is array indices.

0 1 2 3 4 5 6

Sometimes it’s possible answers.

1 2 3 4 5 6 7 8 9 10

The important thing is that every possible answer lies somewhere between low and high.

Initially, the entire range is still under consideration.

low
↓

1 2 3 4 5 6 7 8 9 10
                  ↑
                high

As the algorithm progresses, this range becomes smaller and smaller until there are no candidates left to examine.

2. ans = -1

let ans = -1;

This variable stores the best answer found so far.

Initially, we haven’t found any valid answer, so we initialize it to -1.

Whenever check(mid) returns true, we know that mid satisfies the condition.

Instead of immediately returning it, we save it.

ans = mid;

Why don’t we stop here?

Because mid might not be the best answer.

Suppose our search space looks like this.

1 2 3 4 5 6 7 8

F F F T T T T T

Imagine the first midpoint happens to be 6.

check(6) = true

Great.

We now know that 6 works.

But we’re looking for the first value that works.

Maybe 5 also works.

Maybe 4 works.

So instead of returning immediately, we save 6 in ans and continue searching the left half.

Later we discover that 4 also satisfies the condition.

ans = 6

↓

ans = 4

Every time we find a better candidate, we simply overwrite the previous answer.

When the algorithm finishes, ans contains the optimal answer.

If check() never returns true, ans remains -1, indicating that no valid answer exists.

3. Calculating the Midpoint

const mid = low + Math.floor((high - low) / 2);

The midpoint divides the current search space into two halves.

Suppose our current search space is

1 2 3 4 5 6 7 8 9

The midpoint is

5

Everything to the left

1 2 3 4

forms one half.

Everything to the right

6 7 8 9

forms the other.

The beauty of binary search is that after inspecting just one value, we can confidently discard roughly half of the remaining search space.

Although JavaScript doesn’t suffer from the same integer overflow issues as languages like C++ or Java for normal interview-sized inputs, writing the midpoint as

low + Math.floor((high - low) / 2)

has become the standard because it clearly expresses the intent:

Start at the left boundary, then move halfway toward the right boundary.

4. The check() Function

This is the only part of the algorithm that changes from problem to problem.

if (check(mid))

Everything else stays exactly the same.

Think of check() as a yes-or-no question.

Does this candidate satisfy the required condition?

It always returns one of two values.

true

or

false

That’s all.

The implementation changes depending on the problem, but its purpose never changes.

Once you can write the check() function, the rest of the binary search is almost mechanical.

5. The Branching Logic

Now we reach the most important part of the algorithm.

if (check(mid)) {
    ans = mid;
    high = mid - 1;
} else {
    low = mid + 1;
}

At first glance, these four lines seem arbitrary.

Why do we move high when check(mid) is true?

Why do we move low when it’s false?

Why do we use mid - 1 instead of mid?

When check(mid) is true

Suppose our search space looks like this.

1 2 3 4 5 6 7 8 9

F F F F T T T T T

Our goal is to find the first true.

Imagine the midpoint is 6.

check(6) = true

This tells us two things.

First,

6 is a valid answer.

So we save it.

ans = mid;

Second,

since we’re looking for the first true, there might still be a better answer somewhere to the left.

Maybe 5 is also true.

Maybe 4 is the first true.

So instead of stopping, we continue searching the left half.

high = mid - 1;

Notice that we remove mid from the search space.

We’ve already checked it.

We’ve already saved it.

There is no reason to examine it again.

When check(mid) is false

Now suppose the midpoint is 3.

check(3) = false

Since the predicate is monotonic,

1
2
3

must also be false.

There is absolutely no reason to search that portion again.

The answer, if it exists, must lie to the right.

So we discard everything up to and including mid.

low = mid + 1;

Again, notice that mid is removed from the search space.

Once it has been evaluated, it never needs to be visited again.

Why Do We Use mid - 1 and mid + 1?

A useful way to think about this template is:

Every iteration completely removes mid from the search space.

Once we’ve evaluated check(mid), that value has served its purpose.

Either

• it was valid and we’ve already stored it in ans, or
• it was invalid and can never become valid later.

Keeping mid inside the search space would only cause us to examine it again.

Using

high = mid - 1;

and

low = mid + 1;

guarantees that every iteration makes progress by removing at least one value.

Why while (low <= high)?

This naturally leads to another question.

If we’re removing mid every iteration, why do we write

while (low <= high)

instead of

while (low < high)

The answer is that these two choices are connected.

You cannot change one without changing the other.

Understanding the Search Space

Suppose our search space eventually shrinks to

low = 7
high = 7

That means only one candidate remains.

7

This candidate has never been examined before.

It still deserves one final check.

With

while (low <= high)

the loop executes one last iteration.

const mid = 7;

Now we evaluate

check(7)

and then remove it.

If it’s true,

ans = 7;
high = 6;

If it’s false,

low = 8;

Either way, the search space becomes empty.

low = 8
high = 6

Now

low <= high

is false, so the algorithm stops.

Every possible candidate has been examined exactly once.

What Goes Wrong with low < high?

Suppose we keep the exact same pointer updates.

if (check(mid)) {
    ans = mid;
    high = mid - 1;
} else {
    low = mid + 1;
}

but change the loop to

while (low < high)

Again we eventually reach

low = 7
high = 7

Now the condition becomes

7 < 7

which is false.

The loop exits immediately.

The last remaining candidate is never checked.

This is a subtle off-by-one error.

Sometimes it still works because the answer was discovered earlier.

Sometimes it fails because the last remaining candidate happens to be the correct answer.

Those are the hardest bugs to find because they only appear on certain edge cases.

## Why Do Other Templates Use low < high?

If you’ve read other articles, you’ve probably seen another template.

~~while (low < high) {~~
~~    const mid = low + Math.floor((high - low) / 2);~~

~~    if (check(mid)) {~~
~~        high = mid;~~
~~    } else {~~
~~        low = mid + 1;~~
~~    }~~
~~}~~

~~return low;~~

Notice the difference.

When check(mid) is true, this version does

~~high = mid;~~

instead of

~~high = mid - 1;~~

That small change completely changes the algorithm.

Unlike our template, this version keeps mid inside the search space.

Suppose

~~low = 5~~
~~high = 6~~

The midpoint becomes

~~mid = 5~~

If check(5) is true,

~~high = mid;~~

gives

~~low = 5~~
~~high = 5~~

Notice something important.

The value 5 has not been removed.

It remains inside the search space.

Eventually the loop stops when

~~low == high~~

At that point,

the remaining value is guaranteed to be the answer because it has intentionally been kept alive throughout the search.

This version therefore doesn’t need an ans variable.

## Two Templates, Two Different Ideas

Both templates are correct.

They simply follow different philosophies.

### This Template

~~while (low <= high)~~

~~high = mid - 1;~~
~~low = mid + 1;~~

* mid is removed immediately. * Every candidate is checked exactly once. * Valid answers are stored in ans. * The search continues looking for a better answer.

---

### Alternative Template

~~while (low < high)~~

~~high = mid;~~
~~low = mid + 1;~~

* mid is sometimes kept. * The answer always remains inside the search space. * The search stops when only one candidate remains. * No ans variable is required.

Neither template is better.

The important thing is not mixing them.

Using

~~while (low <= high)~~

together with

~~high = mid;~~

can cause infinite loops because the search space may never shrink.

Likewise, using

~~while (low < high)~~

with

~~high = mid - 1;~~

can skip the final candidate entirely.

Always treat the loop condition and the pointer updates as a single unit.

Visualizing the Entire Search

Suppose

check(x) = x >= 7

Searching over

0 1 2 3 4 5 6 7 8 9

The predicate looks like this.

F F F F F F F T T T

Let’s trace the algorithm.

Iteration 1

low = 0
high = 9
mid = 4

check(4) = false

Move right.

low = 5
high = 9

Iteration 2

mid = 7

check(7) = true

Save it.

ans = 7;

Search left.

low = 5
high = 6

Iteration 3

mid = 5

check(5) = false

Move right.

low = 6
high = 6

Iteration 4

mid = 6

check(6) = false

Move right.

low = 7
high = 6

The search space is now empty.

The answer stored in ans is

7

Exactly the first value where the predicate became true.

Summary

Whenever you use this template, remember these rules:

The most important thing to remember is that this template is built around eliminating mid after every iteration. Once you understand that idea, the rest of the algorithm becomes much easier to reason about.

Rather than memorizing the code, memorize the mental model:

Evaluate mid, save it if it’s valid, remove it from the search space, and continue searching only where a better answer could still exist.

Once that clicks, the template becomes almost impossible to forget.

Problems Solved by This Template

69. Sqrt(x)

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let [left, right] = [0, x];
  let answer = -1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (mid * mid <= x) {
      answer = mid;
      left = mid + 1;
    } else right = mid - 1;
  }
  return answer;
};

35. Search Insert Position

function lowerBound(arr, x) {
  let low = 0, high = arr.length - 1;
  let ans = arr.length;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    // maybe an answer
    if (arr[mid] >= x) {
      ans = mid;
      //look for smaller index on the left
      high = mid - 1;
    }
    else {
      low = mid + 1; // look on the right
    }
  }
  return ans;
}
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  return lowerBound(nums, target);
};

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

const binarySearch = (array, target, left = true) => {
  let [low, high] = [0, array.length - 1];
  let result = -1;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    if (array[middle] == target) {
      result = middle;
      if (left) high = middle - 1;
      if (!left) low = middle + 1;
    }
    else if (target < array[middle]) high = middle - 1;
    else low = middle + 1;
  }

  return result;
}
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  if (!nums || !nums.length) return [-1, -1];
  const leftMost = binarySearch(nums, target);
  const rightMost = binarySearch(nums, target, false);
  return [leftMost, rightMost];
};

278. First Bad Version

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
      let low = 1;
      let high = n;
      let result = -1;
      while(low <= high) {
        const middle = Math.floor((low + high) / 2);
        if (isBadVersion(middle)) {
          result = middle;
          high = middle - 1;
        } else {
          low = middle + 1;
        }
      }
      return result;
    };
};

1011. Capacity To Ship Packages Within D Days

const canShip = (weights, weightChoosen, days) => {
  let daysSoFar = 1;
  let runningSum = 0;
  for (let i = 0; i < weights.length; i++) {
    runningSum += weights[i];
    if (runningSum > weightChoosen) {
      daysSoFar++;
      runningSum = weights[i]
    }
  }
  return daysSoFar <= days;
}
const sum = array => array.reduce((prev, curr) => prev + curr, 0);
/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function (weights, days) {

  let [low, high] = [Math.max(...weights), sum(weights)];
  let ans = high;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    if (canShip(weights, middle, days)) {
      ans = middle;
      high = middle - 1;
    } else {
      low = middle + 1;
    }
  }
  return ans;
};

1482. Minimum Number of Days to Make m Bouquets

const check = (bloomDay, middleValue, m, k) => {
  let [boquets, flowers] = [0, 0];
  for (let i = 0; i < bloomDay.length; i++) {
    if (bloomDay[i] <= middleValue) {
      flowers++;
    } else {
      flowers = 0;
    }

    if (flowers == k) {
      boquets++;
      flowers = 0;
    }
  }
  return boquets >= m;
}
/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
var minDays = function (bloomDay, m, k) { // m boquet, k flower
  if (m * k > bloomDay.length) return -1;
  let [low, high] = [Math.min(...bloomDay), Math.max(...bloomDay)];
  let answer = -1;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    if (check(bloomDay, middle, m, k)) {
      answer = middle;
      high = middle - 1;
    } else low = middle + 1;
  }
  return answer;
};

875. Koko Eating Bananas

const timeTaken = (pile, step) => {
  return Math.ceil(pile / step);
};
const timeForPiles = (piles, step) => {
  let totalTime = 0;
  for (const pile of piles) {
    totalTime += timeTaken(pile, step);
  }
  return totalTime;
};
/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
  let [low, high] = [0, Math.max(...piles)];
  let answer = high;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    const value = timeForPiles(piles, middle);
    if (value <= h) {
      answer = middle;
      high = middle - 1;
    } else {
      low = middle + 1;
    }

  }
  return answer;
};