cf.completefrontend
SEARCHING & BINARY SEARCH · CORE

Lower and upper bound

Use binary search to find the first position where a value could go in a sorted list, before or after any equal values.

Time O(log n)Space O(1)9 practice problemsStep-through picture

The idea

Plain binary search answers "where is this value?". Lower and upper bound answer a slightly different question: "where does this value start, and where does it end?". They work even when the list has repeats, and even when the value is not in the list at all.

The lower bound of target is the first index whose item is greater than or equal to target. The upper bound is the first index whose item is strictly greater than target. In [1, 3, 3, 3, 5] with target 3, the lower bound is 1 and the upper bound is 4. The copies of 3 sit from index 1 up to, but not including, index 4.

These two numbers answer many questions at once. How many times does 3 appear? 4 - 1 = 3. Where should a new 3 go to keep the list sorted? At the lower bound or the upper bound. How many items are smaller than 3? Exactly the lower bound, 1.

An everyday example

Finding where a name goes on a sorted guest list

You have a guest list sorted by last name, and three people are named Lee. A new guest named Lee arrives. You can write the new name just before the first Lee, or just after the last Lee. To find either spot you don't read the list from the top: you open it near the middle, see if you are too early or too late, and keep halving. The spot before the first Lee is the lower bound. The spot after the last Lee is the upper bound.

How the example maps to the code
In the exampleIn the code
The sorted guest listThe sorted array items
The spot just before the first LeelowerBound(items, target)
The spot just after the last LeeupperBound(items, target)
How many Lees there areupperBound(...) - lowerBound(...)

From the slow way to lower and upper bound

  1. Start with plain binary search on [2, 6, 6, 6, 6, 11, 14], looking for 6. Its first middle check lands on index 3, holds a 6, and stops. That answers "is it there?", but not "where do the 6s start?" or "how many are there?". Walking left and right from index 3 to find the edges costs O(n) when most items are copies.
  2. Change the question so it has exactly one answer: the first index whose item is >= target. Every item now falls into one of two groups: items < target on the left and items >= target on the right. The answer is the border between the groups. There is exactly one border, even with copies, and even when target isn't in the list.
  3. The border can sit after the last item, so the possible answers run from 0 to items.length: one more spot than there are items. That is why high starts at items.length. And when items[mid] >= target, mid itself might be the border, so keep it in the range with high = mid instead of throwing it away.
  4. When items[mid] < target, mid is on the left side, so the border is after it: low = mid + 1. Each step shrinks the range, and when low === high only one spot is left, which is the border. Change < to <= and the same loop finds the first item > target. Those two loops are lower and upper bound.

How it works

  1. Set low = 0 and high = items.length. Note that high starts one past the last index, because the answer can be "after every item".
  2. While low < high, pick mid = Math.floor((low + high) / 2).
  3. For the lower bound: if items[mid] < target, the answer is to the right of mid, so set low = mid + 1.
  4. Otherwise items[mid] is big enough to be the answer, so keep it in range: set high = mid.
  5. When low equals high, the range has one spot left. That spot is the answer: return low.
  6. The upper bound is the same loop with one change: move right when items[mid] <= target, so equal values are skipped too.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function lowerBound(items, target) {
  2. let low = 0;
  3. let high = items.length;
  4. while (low < high) {
  5. const mid = Math.floor((low + high) / 2);
  6. if (items[mid] < target) {
  7. low = mid + 1;
  8. } else {
  9. high = mid;
  10. }
  11. }
  12. return low;
  13. }
  15. function upperBound(items, target) {
  16. let low = 0;
  17. let high = items.length;
  18. while (low < high) {
  19. const mid = Math.floor((low + high) / 2);
  20. if (items[mid] <= target) {
  21. low = mid + 1;
  22. } else {
  23. high = mid;
  24. }
  25. }
  26. return low;
  27. }

How fast it is

TimeO(log n)
Extra memoryO(1)

Each loop halves the range from low to high, so each bound takes about log₂ n steps. Only a few numbers are stored.

  • Best caseO(log n)

    There is no early exit on a match: the loop always runs until low === high. Even a list made only of copies of target takes about log₂ n steps.

  • Average caseO(log n)

    Any target: the range of n + 1 possible spots halves with each check.

  • Worst caseO(log n)

    About log₂ (n + 1) checks per bound, around 20 for a million items, whether the target appears zero times or a million times.

Common mistakes

  • Mixing the two styles: using high = items.length - 1 and while (low <= high) from plain binary search together with high = mid. The loop can run forever. Pick one style and keep all three parts of it.
  • Writing high = mid - 1 in the lower bound. When items[mid] is the first big-enough item, it gets thrown away and the answer comes out one too far right.
  • Forgetting that the lower bound can be items.length. Reading items[low] then gives undefined. Check low < items.length before you read.
  • Using < in the upper bound instead of <=. Then it returns the lower bound again, and every count comes out 0.

When to use it

Look for these clues in a problem:

  • The list is sorted and may contain repeated values.
  • You need the first or last position of a value, or how many times it appears.
  • You need where to insert a value so the list stays sorted.
  • You need how many items are smaller than, at most, or at least some value.
  • You need all items inside a range, such as every event between two times.

Check yourself

Answer each one in your head first, then open it.

Why does high start at items.length and not items.length - 1?

Because the answer can be "after every item", which is index items.length. Starting one lower would make that answer impossible to return.

In [3, 3, 3], what do the two bounds return for target 3, and what does their difference mean?

The lower bound is 0 and the upper bound is 3. The difference, 3, is how many times 3 appears.

What goes wrong if the lower bound uses high = mid - 1?

When mid is the first big-enough item, it gets thrown away. In [1, 3, 5] with target 3, the loop then returns 0, an index whose item is too small.

How can you check whether target is in the list using only lowerBound?

Compute i = lowerBound(items, target) and test i < items.length && items[i] === target. If either part fails, the value isn't there.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 9 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The lower bound keeps two promises at the top of every loop: every index before low holds an item < target, and every index from high to the end holds an item >= target. At the start, low = 0 and high = items.length, so both groups are empty and both promises are true.

Each step keeps them. If items[mid] < target, then mid belongs to the left group, and because the list is sorted, so does everything before it: low = mid + 1 is safe. Otherwise items[mid] >= target, and every item after mid is too, so high = mid is safe. Since mid is at least low and less than high, the range really shrinks every time.

The loop ends when low === high. Then every index before low is < target and every index from low on is >= target, so low is exactly the first index whose item is >= target. The upper bound uses the same proof with <= target in place of < target.

Going deeper

3 more ideas

Why the answer is always inside the range

Think of the list as two parts: items that are too small (items[i] < target) on the left, and items that are big enough on the right. The lower bound is where the second part starts. The loop keeps this rule: every index before low is too small, and every index from high on is big enough. Each step moves low or high closer while keeping that rule. When they meet, the meeting point is exactly where "too small" ends.

Why high starts at the length and moves to mid

The answer can be any index from 0 to items.length, which is one more spot than there are items. That is why high = items.length. When items[mid] is big enough, mid itself might be the answer, so we can't throw it away: high = mid, not mid - 1. The loop uses low < high because when they are equal, one spot is left and it must be the answer, so there is nothing more to check.

Finding a value, and counting a range

To check if target is present, compute i = lowerBound(items, target) and test i < items.length && items[i] === target. To count items between a and b, inclusive, use upperBound(items, b) - lowerBound(items, a). Each answer costs two binary searches, so O(log n).

Work it by hand

Every step in a table, with why

Find both bounds of 6 in a sorted list where it appears four times.

items = [2, 6, 6, 6, 6, 11, 14], target = 6

StepBoundlowhighmiditems[mid]What happensWhy
1lower07366 < 6 is false, so high = 3items[3] is big enough, so it might be the first 6. Keep it in the range.
2lower03166 < 6 is false, so high = 1Another 6, and it might still be the first one.
3lower01022 < 6, so low = 12 is too small, so the border is after index 0.
4lower11--low === high: return 1One spot is left, so it must be the border. The first 6 is at index 1.
5upper07366 <= 6, so low = 4The only change: an equal item now counts as "too small", so the search moves right past it.
6upper4751111 <= 6 is false, so high = 511 is bigger than 6, so it might be the first item past the copies.
7upper45466 <= 6, so low = 5Index 4 holds the last 6, so the border is after it.
8upper55--low === high: return 5Index 5, holding 11, is the first item bigger than 6.

The lower bound is 1 and the upper bound is 5, so 6 appears 5 - 1 = 4 times, at indexes 1 to 4. Each bound took 3 checks, and neither loop walked over the copies one by one.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Lower and upper boundO(log n)O(1)The list is sorted and you need first or last positions, counts, or insert spots, possibly many times.
Binary search, then walk outwardO(n)O(1)Only when copies are known to be rare, so the walk is short. With many copies it becomes a linear scan.
Linear scan for the edgesO(n)O(1)The list is tiny or not sorted, and you only ask once.
Hash map of countsO(1)O(n)You only need how many times each value appears, never positions or ranges, and building the map once is fine.

Extra memory: O(1): just low, high, and mid.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Lower and upper bound and the other approaches, on a scale where each line up is 10 times more steps.
  • Lower and upper bound O(log n)
  • Binary search, then walk outward, Linear scan for the edges O(n)
  • Hash map of counts O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Lower and upper bound31020
Binary search, then walk outward101,0001 million
Linear scan for the edges101,0001 million
Hash map of counts111

Inputs that need care

5 tricky inputs
An empty list: items = []
low and high both start at 0, so the loop never runs and both bounds return 0: insert at the start, zero copies.
A target bigger than everything: [2, 6, 6, 6, 6, 11, 14], target 20
Every check moves low right, and the lower bound returns 7, which is items.length. Reading items[7] gives undefined, so check i < items.length before reading.
A target missing but inside the range: same list, target 7
Both bounds return 5, the index of 11. Equal bounds mean zero copies, and 5 is where a 7 would be inserted.
A target smaller than everything: same list, target 1
Both bounds return 0. Every item is bigger than 1, so the border is at the very start.
All items equal: [4, 4, 4, 4], target 4
The lower bound is 0 and the upper bound is 4, so the count is 4. This is the input where walking outward from a match would have been slowest.

Variations and follow-ups

Twists interviewers add

Last index of a value

The last copy of target sits at upperBound(items, target) - 1, if that index holds target. In the trace, that is 5 - 1 = 4. This avoids writing a third, slightly different loop.

Search with any yes-or-no test

Replace items[mid] < target with any test that is true for a first part of the list and false after it, such as rows[mid].top + rows[mid].height <= scrollTop. The loop returns the first index where the test turns false. This general form is often called a partition point.

Counting in a range

Items between a and b, inclusive, number upperBound(items, b) - lowerBound(items, a). Items strictly less than x number lowerBound(items, x), and items at most x number upperBound(items, x). Each count costs one or two O(log n) searches.

Sorted insert

To keep a list sorted while adding items, find the spot with upperBound and call items.splice(spot, 0, value). Using the upper bound keeps equal items in the order they arrived. The search is O(log n), but splice shifts items and costs O(n).

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "first position", "last position", "how many times", "where would it be inserted", or "how many items are less than x" on sorted data.
  • Say the two groups out loud: "before low everything is too small, from high on everything is big enough". That one sentence explains high = items.length, high = mid, and low < high.
  • Don't mix styles. Use low < high with high = items.length and high = mid, and don't combine them with low <= high and mid - 1 from plain binary search. Test with a target bigger than every item, which must return items.length.
  • A common follow-up: "return the first and last index, or [-1, -1] if it's missing". Answer: first = lowerBound(items, target); if first === items.length or items[first] !== target, return [-1, -1]; otherwise the last index is upperBound(items, target) - 1.

Where frontend code uses it

The same idea in real UI code
  • A virtualized list knows each row's top position, sorted. The first visible row is a bound search for scrollTop, and the last visible row is a bound search for scrollTop + viewportHeight.
  • Zooming a chart to a time range: two bound searches over sorted timestamps give the slice of points to draw, without scanning every point.
  • Inserting a new message into a chat list that is sorted by time: the upper bound of its timestamp is the index to splice it in, after any messages with the same time.

Related algorithms