Lower and Upper Bounds

Introduction

Lower bound and upper bound are search techniques used to find the position where a value fits (or would fit) within a sorted collection. They answer questions like "where does this value start?" and "where does this value end?" — and they do it in O(log n) time using variations of binary search. These operations are essential for range queries, counting occurrences, and solving a huge class of interview problems efficiently.

The Real-World Analogy

Imagine you're at a library where books are arranged by publication year on a long shelf. A librarian asks you to pull out all books published between 2010 and 2020.

You don't scan every single book. Instead, you:

1. Use a quick halving strategy to find where the 2010 section starts (lower bound of 2010).
2. Use the same strategy to find where the 2020 section ends (upper bound of 2020).
3. Grab everything in between.

That's exactly what lower and upper bounds do with sorted data.

Core Concepts

Definitions

Term	Definition	Returned Position
Lower Bound	The first position where the value could be inserted without breaking the sort order. Equivalently, the index of the first element ≥ target.	leftmost index where arr[i] >= target
Upper Bound	The position just past the last occurrence of the target. Equivalently, the index of the first element > target.	leftmost index where arr[i] > target

Both return an index between 0 and arr.length (inclusive of arr.length, meaning "past the end").

Visual Example

Given the sorted array:

Index:  0  1  2  3  4  5  6  7  8
Value:  1  2  4  4  4  6  7  8  9

For target = 4:

• Lower Bound → 2 (first index where value ≥ 4)
• Upper Bound → 5 (first index where value > 4)
• Count of 4s = upper - lower = 5 - 2 = 3 ✓

For target = 5 (not present):

• Lower Bound → 5 (first index where value ≥ 5, which is the element 6)
• Upper Bound → 5 (first index where value > 5, also the element 6)
• Count of 5s = 5 - 5 = 0 ✓

How They Differ from Standard Binary Search

Standard binary search finds any occurrence of a target and returns immediately. Lower and upper bounds keep searching even after finding a match, because they need the boundary positions.

Implementation

Lower Bound

The key insight: when arr[mid] >= target, we don't stop — we record this as a candidate and keep looking left for an even earlier position.

/**
 * Returns the index of the first element >= target.
 * If all elements are smaller, returns arr.length.
 */
function lowerBound(arr, target) {
  let lo = 0;
  let hi = arr.length; // NOTE: hi starts at arr.length, not arr.length - 1

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // avoids overflow
    if (arr[mid] < target) {
      lo = mid + 1; // mid is too small, discard left half
    } else {
      hi = mid; // arr[mid] >= target, could be the answer — search left
    }
  }

  return lo; // lo === hi, the insertion point
}

// --- Demo ---
const arr = [1, 2, 4, 4, 4, 6, 7, 8, 9];
console.log(lowerBound(arr, 4));  // 2
console.log(lowerBound(arr, 5));  // 5
console.log(lowerBound(arr, 1));  // 0
console.log(lowerBound(arr, 10)); // 9 (past the end)
console.log(lowerBound(arr, 0));  // 0 (before everything)

Upper Bound

Almost identical, but the condition flips from < to <=:

/**
 * Returns the index of the first element > target.
 * If all elements are <= target, returns arr.length.
 */
function upperBound(arr, target) {
  let lo = 0;
  let hi = arr.length;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] <= target) {
      lo = mid + 1; // mid is <= target, discard left half
    } else {
      hi = mid; // arr[mid] > target, could be the answer — search left
    }
  }

  return lo;
}

// --- Demo ---
const arr = [1, 2, 4, 4, 4, 6, 7, 8, 9];
console.log(upperBound(arr, 4));  // 5
console.log(upperBound(arr, 5));  // 5
console.log(upperBound(arr, 9));  // 9 (past the end)
console.log(upperBound(arr, 0));  // 0

Side-by-Side Comparison

The only difference between the two functions is a single character: < vs <=.

Step-by-Step Walkthrough

Let's trace lowerBound([1, 2, 4, 4, 4, 6, 7, 8, 9], 4):

Step	lo	hi	mid	arr[mid]	Condition	Action
1	0	9	4	4	4 < 4? No	hi = 4
2	0	4	2	4	4 < 4? No	hi = 2
3	0	2	1	2	2 < 4? Yes	lo = 2
4	lo == hi == 2	—	—	—	Loop ends	Return 2

Common Use Cases and Patterns

1. Counting Occurrences of a Value

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

const arr = [1, 2, 4, 4, 4, 6, 7, 8, 9];
console.log(countOccurrences(arr, 4)); // 3
console.log(countOccurrences(arr, 5)); // 0
console.log(countOccurrences(arr, 1)); // 1

2. Range Queries — "How many values fall in [lo, hi]?"

function countInRange(arr, from, to) {
  // Number of elements in [from, to] inclusive
  return upperBound(arr, to) - lowerBound(arr, from);
}

const arr = [1, 2, 4, 4, 4, 6, 7, 8, 9];
console.log(countInRange(arr, 3, 7)); // 5 (elements: 4,4,4,6,7)
console.log(countInRange(arr, 4, 4)); // 3 (three 4s)

3. Finding the Insertion Point

Lower bound directly gives you the position to insert a value while maintaining sorted order — this is exactly what Python's bisect_left and C++'s std::lower_bound do.

function insertSorted(arr, value) {
  const pos = lowerBound(arr, value);
  arr.splice(pos, 0, value);
  return arr;
}

console.log(insertSorted([1, 3, 5, 7], 4)); // [1, 3, 4, 5, 7]
console.log(insertSorted([1, 3, 5, 7], 5)); // [1, 3, 5, 5, 7] — inserted before existing 5

4. First and Last Position of a Target

A very common interview question (LeetCode 34):

function searchRange(arr, target) {
  const left = lowerBound(arr, target);
  const right = upperBound(arr, target) - 1;

  // Check if target actually exists
  if (left > right || left >= arr.length || arr[left] !== target) {
    return [-1, -1];
  }

  return [left, right];
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // [-1, -1]
console.log(searchRange([], 0));                    // [-1, -1]

The "Bisect" Generalization

Lower and upper bounds are really two instances of a more general concept: bisecting on a predicate. Given a sorted boolean condition, find where it flips from false to true.

• Lower bound uses predicate: arr[i] >= target
• Upper bound uses predicate: arr[i] > target

This generalization lets you solve non-obvious problems like "find the minimum speed to finish within a time limit" — the answer space is sorted by the predicate, and you bisect it.

/**
 * Generalized bisect: finds the smallest index in [lo, hi) where predicate(index) is true.
 * Assumes predicate is false then true (monotonic).
 */
function bisect(lo, hi, predicate) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (predicate(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  return lo;
}

// Lower bound rewritten using bisect:
function lowerBound(arr, target) {
  return bisect(0, arr.length, (i) => arr[i] >= target);
}

// Upper bound rewritten using bisect:
function upperBound(arr, target) {
  return bisect(0, arr.length, (i) => arr[i] > target);
}

Advanced Example: "Binary Search the Answer"

Many interview problems don't look like search problems at first glance, but they can be solved with bounds. Here's a classic:

Problem: Koko has n piles of bananas. She can eat at most speed bananas per hour (one pile per hour, even if she finishes early). Find the minimum speed to eat all bananas in h hours.

function minEatingSpeed(piles, h) {
  // The answer is in range [1, max(piles)]
  // We need the lower bound where "can finish in time" becomes true
  
  function canFinish(speed) {
    let hours = 0;
    for (const pile of piles) {
      hours += Math.ceil(pile / speed);
    }
    return hours <= h;
  }

  let lo = 1;
  let hi = Math.max(...piles);

  // Lower bound on speed where canFinish is true
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canFinish(mid)) {
      hi = mid; // can finish, try slower
    } else {
      lo = mid + 1; // too slow, go faster
    }
  }

  return lo;
}

console.log(minEatingSpeed([3, 6, 7, 11], 8));  // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5)); // 30

Complexity Analysis

Operation	Time	Space
Lower Bound	O(log n)	O(1)
Upper Bound	O(log n)	O(1)
Count occurrences	O(log n)	O(1)
Range count [a, b]	O(log n)	O(1)

Compare this to a linear scan which would be O(n) — for an array of 1 million elements, binary search does ~20 comparisons vs 1,000,000.

Common Pitfalls

1. Off-by-One Errors

The most common source of bugs. Remember:

• hi starts at arr.length (not arr.length - 1) because the answer could be "past the end"
• The loop condition is lo < hi (not lo <= hi)
• We never use mid - 1 for hi — we set hi = mid

2. Infinite Loops

If you write hi = mid - 1 paired with lo < hi, or lo = mid paired with lo < hi, you risk infinite loops. The safe pattern is:

lo = mid + 1  (always advances)
hi = mid       (always advances because mid < hi when lo < hi)

3. Integer Overflow in Mid Calculation

Always use lo + Math.floor((hi - lo) / 2) instead of Math.floor((lo + hi) / 2). In JavaScript with safe integers this isn't usually a problem, but in Java or C++ with int, lo + hi can overflow.

Language Built-ins

You don't always need to code these from scratch:

Language	Lower Bound	Upper Bound
C++	std::lower_bound()	std::upper_bound()
Python	bisect.bisect_left()	bisect.bisect_right()
Java	Collections.binarySearch() (needs adaptation)	—
JavaScript	None built-in	None built-in

In interviews, you're typically expected to implement them yourself. Knowing the built-ins shows breadth, but coding them shows depth.

Best Practices

1. Always establish the invariant first: Before writing a single line of code, define what lo and hi represent. A common convention: the answer is always in [lo, hi) — lo is inclusive, hi is exclusive.

2. Use the predicate framework: Reduce any lower/upper bound problem to "find where the boolean condition flips." This makes the logic crystal clear and reusable.

3. Test edge cases systematically: Always verify with: empty array, single element, target smaller than all elements, target larger than all elements, and all elements equal to target.

4. Prefer the safe mid formula: lo + Math.floor((hi - lo) / 2) prevents overflow and is a good habit across all languages.

5. Don't conflate with standard binary search: Lower/upper bounds never return early when they find the target. If you catch yourself writing return mid, you've likely switched to standard binary search.

6. Draw the number line: When debugging, sketch the array with lo, hi, and mid marked. Most bugs become obvious visually.

7. Count via subtraction: Whenever you need the count of elements in a range, use upperBound(hi) - lowerBound(lo). Don't try to count with a single bound.

Related Concepts

• Binary Search — Lower and upper bounds are variations of binary search. Understanding vanilla binary search is a prerequisite.
• Binary Search Trees — BSTs maintain sorted order dynamically, and finding lower/upper bounds in a BST follows the same left/right decision logic.
• Merge Sort — Produces the sorted array that lower/upper bounds operate on. Also uses the divide-and-conquer pattern.
• Two Pointers — Often used alongside bounds for range-based problems on sorted arrays.
• Segment Trees and Binary Indexed Trees (Fenwick Trees) — For more complex range queries on dynamic data where re-sorting isn't practical.

Practice Problems

Here are problems where lower and upper bound techniques are essential:

Problem	Platform	Link
Find First and Last Position of Element in Sorted Array	LeetCode	LeetCode 34
Koko Eating Bananas	LeetCode	LeetCode 875
Search Insert Position	LeetCode	LeetCode 35
Count of Smaller Numbers After Self	LeetCode	LeetCode 315
Minimum Number of Days to Make m Bouquets	LeetCode	LeetCode 1482
Pairs – Pair counting	HackerRank	HackerRank Pairs
Ice Cream Parlor	HackerRank	HackerRank Ice Cream Parlor
Aggressive Cows (binary search on answer)	SPOJ	SPOJ AGGRCOW

Start with LeetCode 35 (Search Insert Position) — it's literally the lower bound function. Then move to LeetCode 34 which combines both bounds. Once comfortable, tackle the "binary search the answer" problems like LeetCode 875 and 1482, which apply the predicate generalization to non-obvious domains.