Finding Lower Bound and Upper Bound Using Binary Search

In the previous post, we built a standard binary search that looks for an exact value. In this one, we’ll slightly modify that template to implement lower bound and upper bound, similar to C++‘s lower_bound() and upper_bound().

The nice thing is that both functions use almost the same binary search template. The only real difference is the comparison we make inside the loop.

Upper Bound

An upper bound returns the index of the first element that is strictly greater than the target.

Instead of searching for the target itself, think of it as searching for the point where the array stops being <= target and starts being > target.

If every element is less than or equal to the target, then there is no such element, so we simply return nums.length.

Consider this sorted array:

Index :  0  1  2  3  4  5  6
Value : [1, 2, 4, 4, 4, 6, 8]

Some examples:

upperBound(nums, 4) = 5

The first value greater than 4 is 6 at index 5.

upperBound(nums, 5) = 5

5 doesn't exist in the array.
The first value greater than 5 is still 6 at index 5.

upperBound(nums, 0) = 0

Everything in the array is greater than 0,
so the answer is the first index.

upperBound(nums, 8) = 7

Nothing is greater than 8,
so we return nums.length.

One useful property of upper bound is that it also tells us how many elements are less than or equal to the target.

Starting from the standard binary search

Here’s the usual binary search implementation:

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;
}

To turn this into upperBound, we only need three changes.

Remove the === target case. We’re not looking for an exact match anymore.
Keep track of the best answer seen so far.
If we never find a valid answer, return nums.length.

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

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

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

  return ans;
}

Dry run

Let’s walk through upperBound(nums, 4).

Index :  0  1  2  3  4  5  6
Value : [1, 2, 4, 4, 4, 6, 8]

Initially:

low = 0
high = 6
ans = 7

Iteration 1

mid = (0 + 6) / 2 = 3

nums[3] = 4

Is 4 > 4?

No.

That means every element up to index 3 is still <= target, so the answer has to be somewhere on the right.

low = 4
high = 6
ans = 7

Iteration 2

mid = (4 + 6) / 2 = 5

nums[5] = 6

Is 6 > 4?

Yes.

This is a valid answer, but there might be another element greater than 4 even earlier in the array.

Save it and continue searching to the left.

ans = 5

low = 4
high = 4

Iteration 3

mid = (4 + 4) / 2 = 4

nums[4] = 4

Is 4 > 4?

No.

low = 5
high = 4

The loop stops because low > high.

Our answer is:

ans = 5

which is exactly the first index containing a value greater than 4.

Notice that we didn’t stop as soon as we found 6. We kept searching to the left because we wanted the first valid index.

Why this works

A useful way to think about binary search is that you’re looking for a boundary, not necessarily a value.

For upper bound, every element belongs to one of two groups:

<= target | > target

Since the array is sorted, those groups appear consecutively.

Whenever nums[mid] > target, we know we’ve entered the second group, so we record that index and continue searching to the left to see if the boundary occurs even earlier.

Otherwise, we’re still in the first group, so we move right.

Lower Bound

A lower bound returns the index of the first element that is greater than or equal to the target.

If the target exists, this gives us the index of its first occurrence.

Using the same array:

Index :  0  1  2  3  4  5  6
Value : [1, 2, 4, 4, 4, 6, 8]

Examples:

lowerBound(nums, 4) = 2

The first occurrence of 4 is at index 2.

lowerBound(nums, 5) = 5

5 isn't present, so we return the first value that is >= 5,
which is 6 at index 5.

lowerBound(nums, 0) = 0

Every element satisfies the condition.

lowerBound(nums, 9) = 7

No element is >= 9,
so we return nums.length.

Another useful property is that lowerBound(nums, target) also tells us how many elements are strictly less than the target.

The only change

The implementation is almost identical to upperBound.

The only difference is the comparison.

Instead of checking

nums[mid] > target

we check

nums[mid] >= target

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

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

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

  return ans;
}

Dry run

Let’s walk through lowerBound(nums, 4).

Index :  0  1  2  3  4  5  6
Value : [1, 2, 4, 4, 4, 6, 8]

Initially:

low = 0
high = 6
ans = 7

Iteration 1

mid = (0 + 6) / 2 = 3

nums[3] = 4

Is 4 >= 4?

Yes.

This is a valid answer, but there might be another 4 before it.

ans = 3

low = 0
high = 2

Iteration 2

mid = (0 + 2) / 2 = 1

nums[1] = 2

Is 2 >= 4?

No.

low = 2
high = 2

Iteration 3

mid = (2 + 2) / 2 = 2

nums[2] = 4

Is 4 >= 4?

Yes.

ans = 2

low = 2
high = 1

The loop exits.

The final answer is:

ans = 2

which is the first occurrence of 4.

If you compare both implementations side by side, you’ll notice they’re almost identical.

// upperBound
if (nums[mid] > target) {
  ans = mid;
  high = mid - 1;
} else {
  low = mid + 1;
}

// lowerBound
if (nums[mid] >= target) {
  ans = mid;
  high = mid - 1;
} else {
  low = mid + 1;
}

That single comparison determines whether we’re searching for the first element that’s > the target or the first element that’s >= the target.

Counting occurrences

Lets solve a famous google interview question using upper and lower bound. The question goes something like this:

Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of the target element.

Example 1:
Input: arr = [4, 4, 8, 8, 8, 15, 16, 23, 23, 42], target = 8
Output: 3
Example 2:
Input: arr = [3, 5, 5, 5, 5, 7, 8, 8], target = 6
Output: 0
Example 3:
Input: arr = [3, 5, 5, 5, 5, 7, 8, 8], target = 5
Output: 4

Link to the question

The number of times a value appears is simply the distance between its upper bound and lower bound.

function countOccurrences(nums, target) {
  return upperBound(nums, target) - lowerBound(nums, target);
}

For our example:

countOccurrences(nums, 4); // 3
countOccurrences(nums, 5); // 0

Both lowerBound and upperBound run in O(log n), so counting occurrences also takes O(log n) without scanning the array.

TL;DR

lowerBound(nums, target) returns the first index where nums[i] >= target.
upperBound(nums, target) returns the first index where nums[i] > target.
Both algorithms run in O(log n).
If no valid element exists, both return nums.length.
upperBound(nums, target) - lowerBound(nums, target) gives the number of occurrences of target.

Binary Search: Lower and Upper Bound

Finding Lower Bound and Upper Bound Using Binary Search

Upper Bound

Starting from the standard binary search

Dry run

Iteration 1

Iteration 2

Iteration 3

Why this works

Lower Bound

The only change

Dry run

Iteration 1

Iteration 2

Iteration 3

Counting occurrences

TL;DR