Course contentsShow
← Computer Science
Lesson 811 of 2,87219. Searching and SelectionFree lesson

Upper Bound Search

Find the last position where a value could be inserted while maintaining sorted order.

Upper Bound Search

What you'll learn: You'll learn how to find the rightmost position where you can insert a value into a sorted array while keeping it sorted.

The Core Idea

You already know about lower bound search, which finds the first position where a value could be inserted. Upper bound search finds the last position—or more precisely, the position after the last occurrence of the target value.

Think of it like finding a parking spot on a street: lower bound finds the first available spot at or after your target address, while upper bound finds the spot just past the last house with that address number.

How It Differs from Lower Bound

While lower bound looks for the first position where array[mid] >= target, upper bound searches for the first position where array[mid] > target. This subtle difference means:

  • If the target exists multiple times, upper bound points after all of them
  • If the target doesn't exist, upper bound points to where it would go (same as lower bound in this case)

Example

Given sorted array [1, 3, 3, 3, 5, 7] and target 3:

  • Lower bound returns index 1 (first 3)
  • Upper bound returns index 4 (position after last 3, where 5 is)

This makes upper bound perfect for counting occurrences: upper_bound - lower_bound gives you the count!

The Search Pattern

The algorithm mirrors binary search with one key change: when array[mid] == target, you move left = mid + 1 instead of returning early, because you need to find where values greater than target begin.

Key Takeaway: Upper bound search finds the insertion point after all occurrences of a target value, enabling range queries and duplicate counting in sorted data.