Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Lower Bound & Upper Bound
DSA

Lower Bound & Upper Bound

Learn how to find the first and last valid positions using lower-bound and upper-bound binary search.

Lower and Upper Bound find boundaries in a sorted array:

Lower → first index with value >= target · Upper → first index with value > target

Focus on recognizing:

Insert position / first occurrence / count of target → bounds

Pattern 1: Lower Bound

Watch the lower bound of 2 in [1,2,2,2,5,7] converge to index 1 — then upper − lower counts the three 2s. Press ▶ to animate.

Lower Bound (first element ≥ target)

Find the first index whose value is ≥ target. Uses the half-open range pattern (hi = n): on a match we keep mid as a candidate by moving hi = mid, otherwise discard mid with lo = mid + 1.

Array: [1,2,2,2,5,7], target = 2. We want the FIRST 2. The '>=' comparison keeps equal values as candidates, allowing the search to move left until it finds the first occurrence.

BINARY SEARCH VISUALIZER
Steps –
1
0
2
1
2
2
2
3
5
4
7
5
Target: 2
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        lo = 0, hi = n          // note: hi is n, NOT n-1
                      
                        2
                        while lo < hi:
                      
                        3
                          mid = (lo + hi) / 2
                      
                        4
                          if nums[mid] >= target:
                      
                        5
                            hi = mid            // mid MIGHT be the answer — keep it
                      
                        6
                          else:
                      
                        7
                            lo = mid + 1        // too small — discard mid
                      
                        8
                        return lo                // first index with nums[i] >= target

Finds the first index where nums[i] >= target — which is also the insertion position:

public int lowerBound(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length;      // note: n, not n - 1

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] >= target) {
            hi = mid;          // mid could be the answer — keep it
        } else {
            lo = mid + 1;
        }
    }

    return lo;
}
from bisect import bisect_left

def lower_bound(nums, target):
    lo, hi = 0, len(nums)      # note: n, not n - 1

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] >= target:
            hi = mid           # mid could be the answer — keep it
        else:
            lo = mid + 1

    return lo

# stdlib equivalent: bisect_left(nums, target)
int lowerBound(vector<int>& nums, int target) {
    int lo = 0;
    int hi = nums.size();      // note: n, not n - 1

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] >= target)
            hi = mid;          // mid could be the answer — keep it
        else
            lo = mid + 1;
    }

    return lo;
}

// stdlib equivalent: lower_bound(nums.begin(), nums.end(), target)
function lowerBound(nums, target) {
  let lo = 0,
    hi = nums.length; // note: n, not n - 1

  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);

    if (nums[mid] >= target) hi = mid;
    // mid could be the answer — keep it
    else lo = mid + 1;
  }

  return lo;
}

The boundary template: while (lo < hi) with hi = mid — mid is never discarded because it might be the answer.

Pattern 2: Upper Bound

One character changes everything — >= becomes >:

Upper Bound

Find the first element strictly greater than the target. Equivalent to lower_bound(target + 1).

Array: [1,3,5,5,5,7], target=5. Upper bound = first element > 5 = 7 at index 5.

ARRAY VISUALIZER
Steps –
1
0
3
1
5
2
5
3
5
4
7
5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        lo = 0, hi = n
                      
                        2
                        while lo < hi:
                      
                        3
                          mid = (lo + hi) / 2
                      
                        4
                          if nums[mid] <= target: lo = mid + 1
                      
                        5
                          else: hi = mid
                      
                        6
                        return lo
                      
public int upperBound(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] > target) {   // strictly greater
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    return lo;
}
from bisect import bisect_right

def upper_bound(nums, target):
    lo, hi = 0, len(nums)

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] > target:   # strictly greater
            hi = mid
        else:
            lo = mid + 1

    return lo

# stdlib equivalent: bisect_right(nums, target)
int upperBound(vector<int>& nums, int target) {
    int lo = 0;
    int hi = nums.size();

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] > target)  // strictly greater
            hi = mid;
        else
            lo = mid + 1;
    }

    return lo;
}

// stdlib equivalent: upper_bound(nums.begin(), nums.end(), target)
function upperBound(nums, target) {
  let lo = 0,
    hi = nums.length;

  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);

    if (nums[mid] > target) hi = mid;
    // strictly greater
    else lo = mid + 1;
  }

  return lo;
}

Derived Answers

Both come free once the bounds exist:

first occurrence = lowerBound(target)
last  occurrence = upperBound(target) - 1
count of target  = upperBound(target) - lowerBound(target)

Example on [1, 2, 2, 2, 5, 7], target 2:

lower = 1, upper = 4
range [1..3], count = 3

Every language ships these: Java Collections.binarySearch-style loops, C++ lower_bound/upper_bound, Python bisect_left/bisect_right, JS hand-rolled.

Count = Upper − Lower — no loop over duplicates needed.

Common Mistakes

Using hi = n - 1.

The answer can be n (“insert at the end”) — start with hi = n.

Confusing >= and >.

Lower keeps values equal to target; upper skips past them. One character flips the semantics.

Using lo <= hi.

Boundary search uses while (lo < hi) — you’re converging on a position, not returning from inside the loop.

Complexity

OperationTime
Either boundO(log n)
SpaceO(1)

My Private Notes

Notes are auto-saved locally to this device.