Lower Bound and Upper Bound

Say you have a sorted list of numbers. You want to find where a value fits. Not just “is it there or not” like plain search. You want the first spot where things become greater-than-or-equal to your target. Or the first spot where things become strictly-greater. That is exactly what lower bound and upper bound give you. Let me show you.

📚 What Are Lower Bound and Upper Bound?

Here is the pain first. Plain binary search only tells you yes it exists or no it does not. But many problems need more than that. You want to know where a number would sit. You want to count how many numbers are below it. You want the range of all copies of a value. Plain search cannot answer that cleanly.

So we use two close cousins of binary search.

• Lower bound is the index of the first element that is greater-than-or-equal to the target.
• Upper bound is the index of the first element that is strictly-greater than the target.

Both work on a sorted array. A sorted array means the numbers go from small to large, left to right. Both run in O(log n) time because they jump in halves, just like binary search.

🎯 A Small Example to See the Difference

Let us take this sorted array. The index sits above each value.

index:   0   1   2   3   4   5
value:  10  20  20  20  40  50

Now say the target is 20. Let us read both bounds slowly.

• Lower bound of 20 looks for the first value that is greater-than-or-equal to 20. That is index 1. The value at index 0 is 10, which is too small. Index 1 is the first 20. So lower bound is 1.
• Upper bound of 20 looks for the first value that is strictly-greater than 20. The 20s do not count. The first value bigger than 20 is 40 at index 4. So upper bound is 4.

See the neat trick here? Upper bound minus lower bound gives the count of how many times 20 appears. Here that is 4 - 1 = 3. And yes, there are three 20s. Very handy.

Let us look at a few more targets on the same array.

Notice the target 30. It is not even in the array, yet both bounds return 4 - the spot where 30 would go. And 99 is bigger than everything, so both return 6, which is n. That matches our note from before.

🛠️ How the Loop Works

Both bounds use the same binary-search shape. You keep a window with a low and a high pointer. You look at the middle. Based on a check, you drop one half. You repeat until the window closes. The only thing that changes between the two is the comparison.

Here is the idea in plain words.

• Start with low = 0 and high = n. Note that high is n, not n - 1. We allow the answer to land at the very end.
• Find the middle: mid = (low + high) / 2.
• For lower bound: if the value at mid is greater-than-or-equal to the target, the answer could be mid or to its left. So set high = mid. Otherwise move right with low = mid + 1.
• For upper bound: change only the check. If the value at mid is strictly-greater than the target, set high = mid. Otherwise low = mid + 1.
• When low equals high, that meeting point is your answer.

The single difference is whether equal values are pushed left or right. Lower bound keeps equal values on the right side of the cut. So it lands on the first equal one. Upper bound pushes equal values to the left side of the cut. So it lands past them.

Steps to find Lower Bound

1. Set low = 0 and high = n (the array length).
2. While low is less than high, compute mid = low + (high - low) / 2.
3. If arr[mid] is greater-than-or-equal to the target, set high = mid.
4. Otherwise set low = mid + 1.
5. When the loop ends, return low. That is the lower bound index.

Steps to find Upper Bound

1. Set low = 0 and high = n (the array length).
2. While low is less than high, compute mid = low + (high - low) / 2.
3. If arr[mid] is strictly-greater than the target, set high = mid.
4. Otherwise set low = mid + 1.
5. When the loop ends, return low. That is the upper bound index.

💻 Code in Five Languages

Below, each program builds the same sorted array [10, 20, 20, 20, 40, 50] and finds both bounds for the target 20. Watch the output match what we worked out by hand: lower bound 1, upper bound 4.

#include <stdio.h>

// First index where arr[i] is greater-than-or-equal to target
int lowerBound(int arr[], int n, int target) {
    int low = 0, high = n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= target)
            high = mid;        // answer is mid or to the left
        else
            low = mid + 1;     // answer is to the right
    }
    return low;
}

// First index where arr[i] is strictly-greater than target
int upperBound(int arr[], int n, int target) {
    int low = 0, high = n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] > target)
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

int main(void) {
    int arr[] = {10, 20, 20, 20, 40, 50};
    int n = 6;
    int target = 20;
    printf("Lower bound of %d = %d\n", target, lowerBound(arr, n, target));
    printf("Upper bound of %d = %d\n", target, upperBound(arr, n, target));
    return 0;
}

Lower bound of 20 = 1
Upper bound of 20 = 4

#include <iostream>
#include <vector>
using namespace std;

// First index where arr[i] is greater-than-or-equal to target
int lowerBound(const vector<int>& arr, int target) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= target)
            high = mid;        // answer is mid or to the left
        else
            low = mid + 1;     // answer is to the right
    }
    return low;
}

// First index where arr[i] is strictly-greater than target
int upperBound(const vector<int>& arr, int target) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] > target)
            high = mid;
        else
            low = mid + 1;
    }
    return low;
}

int main() {
    vector<int> arr = {10, 20, 20, 20, 40, 50};
    int target = 20;
    cout << "Lower bound of " << target << " = " << lowerBound(arr, target) << endl;
    cout << "Upper bound of " << target << " = " << upperBound(arr, target) << endl;
    return 0;
}

Lower bound of 20 = 1
Upper bound of 20 = 4

public class Bounds {

    // First index where arr[i] is greater-than-or-equal to target
    static int lowerBound(int[] arr, int target) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= target)
                high = mid;        // answer is mid or to the left
            else
                low = mid + 1;     // answer is to the right
        }
        return low;
    }

    // First index where arr[i] is strictly-greater than target
    static int upperBound(int[] arr, int target) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > target)
                high = mid;
            else
                low = mid + 1;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 20, 20, 40, 50};
        int target = 20;
        System.out.println("Lower bound of " + target + " = " + lowerBound(arr, target));
        System.out.println("Upper bound of " + target + " = " + upperBound(arr, target));
    }
}

Lower bound of 20 = 1
Upper bound of 20 = 4

# First index where arr[i] is greater-than-or-equal to target
def lower_bound(arr, target):
    low, high = 0, len(arr)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] >= target:
            high = mid        # answer is mid or to the left
        else:
            low = mid + 1     # answer is to the right
    return low

# First index where arr[i] is strictly-greater than target
def upper_bound(arr, target):
    low, high = 0, len(arr)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] > target:
            high = mid
        else:
            low = mid + 1
    return low

arr = [10, 20, 20, 20, 40, 50]
target = 20
print(f"Lower bound of {target} = {lower_bound(arr, target)}")
print(f"Upper bound of {target} = {upper_bound(arr, target)}")

Lower bound of 20 = 1
Upper bound of 20 = 4

// First index where arr[i] is greater-than-or-equal to target
function lowerBound(arr, target) {
  let low = 0, high = arr.length;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] >= target)
      high = mid;        // answer is mid or to the left
    else
      low = mid + 1;     // answer is to the right
  }
  return low;
}

// First index where arr[i] is strictly-greater than target
function upperBound(arr, target) {
  let low = 0, high = arr.length;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] > target)
      high = mid;
    else
      low = mid + 1;
  }
  return low;
}

const arr = [10, 20, 20, 20, 40, 50];
const target = 20;
console.log(`Lower bound of ${target} = ${lowerBound(arr, target)}`);
console.log(`Upper bound of ${target} = ${upperBound(arr, target)}`);

Lower bound of 20 = 1
Upper bound of 20 = 4

⏱️ Time and Space Complexity

Both bounds cut the search window in half every step. So a million elements take only about twenty steps. That is the O(log n) win.

⚠️ Common Mistakes

A few traps catch people every time. Watch out for these.

• Setting high = n - 1 instead of high = n. Then the answer can never land at the end. You miss cases where the target is bigger than everything.
• Mixing up the two checks. Lower bound is greater-than-or-equal. Upper bound is strictly-greater. Swap them by accident and your bounds flip.
• Running it on an array that is not sorted. Both bounds only work when the array goes small to large. On unsorted data the result is meaningless.
• Writing mid = (low + high) / 2 on very large arrays where the sum overflows. Use low + (high - low) / 2 to stay safe.
• Forgetting that the returned value is an index, not the element. If you want the value, check the index is less than n first, then read arr[index].

🧩 What You’ve Learned

• ✅ Lower bound is the index of the first element greater-than-or-equal to the target.
• ✅ Upper bound is the index of the first element strictly-greater than the target.
• ✅ Both run on a sorted array using a binary-search loop in O(log n) time.
• ✅ The only difference between them is the comparison: greater-than-or-equal versus strictly-greater.
• ✅ Upper bound minus lower bound gives the count of how many times a value appears.
• ✅ When no element fits, both return n, the position one past the last index.

🚀 What’s Next?

• Binary Search
• Binary Search on Answer