Log inSign up
easyGeeksforGeeksNot Started

Upper Bound

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a sorted array of integers arr and an integer x, find the Upper Bound of x.

The Upper Bound of x is defined as the smallest index `i` (0-based) such that arr[i] > x (strictly greater). If no such element exists (i.e., all elements are less than or equal to x), return the length of the array n.

You must implement an algorithm with O(log n) runtime complexity.

Example 1 · Exact Element Present with Multiple Occurrences:

Input: arr = [2, 3, 6, 7, 8, 8, 11, 11, 11, 12], x = 11
Output: 9
Explanation: The first index where arr[i] > 11 is index 9 (arr[9] = 12).

Example 2 · Target Absent Between Elements:

Input: arr = [2, 3, 6, 7, 8, 8, 11, 12], x = 6
Output: 3
Explanation: The first index where arr[i] > 6 is index 3 (arr[3] = 7).

Example 3 · Target Greater than or Equal to All Elements:

Input: arr = [1, 2, 5, 6], x = 10
Output: 4
Explanation: No element is > 10, so return arr.length = 4.

Constraints:

  • 1 <= arr.length <= 105
  • -109 <= arr[i] <= 109
  • arr is sorted in non-decreasing (ascending) order.
  • -109 <= x <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Differentiate strict inequality (>) in Upper Bound from non-strict (>=) in Lower Bound.
  • Master boundary convergence for range querying in sorted arrays.
  • Understand the STL std::upper_bound implementation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find first element strictly greater than target
  • Finding upper boundary of repeated elements
  • Count occurrences of target using (upper_bound - lower_bound)

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1, ans = n.
  • Calculate mid = low + (high - low) / 2.
  • If arr[mid] > x: ans = mid, high = mid - 1 (search left).
  • If arr[mid] <= x: low = mid + 1 (search right).
  • Return ans.

Connected Patterns:

Lower BoundSearch Insert PositionLast Occurrence of ElementCount Occurrences

1. Linear Scan

Intuition

Scan the array sequentially. The first index i satisfying arr[i] > x is returned. If no element exceeds x, return n.

When to apply: Unsorted collections or very small array sizes.

Algorithm

  1. Step 1: Iterate index i from 0 to arr.length - 1.
  2. Step 2: Check if arr[i] > x.
  3. Step 3: If true, return index i immediately.
  4. Step 4: If loop finishes, return arr.length.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int upperBound(const vector<int>& arr, int x) {
7 for (int i = 0; i < (int)arr.size(); i++) {
8 if (arr[i] > x) return i;
9 }
10 return arr.size();
11}
12
13int main() {
14 vector<int> arr = {2, 3, 6, 7, 8, 8, 11, 11, 11, 12};
15 cout << "Linear Upper Bound for 11: " << upperBound(arr, 11) << endl;
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(N) — Worst case checks all N elements.
  • Space complexity: O(1) — Uses constant auxiliary memory.

2. Recursive Upper Bound

Intuition

Define solve(low, high, ans). Base case: if low > high, return ans. Compute mid. If arr[mid] > x, recurse on (low, mid - 1, mid). Else recurse on (mid + 1, high, ans).

When to apply: Recursive functional approaches.

Algorithm

  1. Step 1: If low > high, return ans.
  2. Step 2: Calculate mid = low + (high - low) / 2.
  3. Step 3: If arr[mid] > x, recurse solve(low, mid - 1, mid).
  4. Step 4: If arr[mid] <= x, recurse solve(mid + 1, high, ans).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int solve(const vector<int>& arr, int low, int high, int x, int ans) {
7 if (low > high) return ans;
8 int mid = low + (high - low) / 2;
9 if (arr[mid] > x) {
10 return solve(arr, low, mid - 1, x, mid);
11 }
12 return solve(arr, mid + 1, high, x, ans);
13}
14
15int upperBound(const vector<int>& arr, int x) {
16 return solve(arr, 0, arr.size() - 1, x, arr.size());
17}
18
19int main() {
20 vector<int> arr = {2, 3, 6, 7, 8, 8, 11, 11, 11, 12};
21 cout << "Recursive Upper Bound: " << upperBound(arr, 11) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval at each recursive level.
  • Space complexity: O(log N) — O(log N) stack frames.

3. Iterative Binary Search Upper Bound (Gold Standard)

Intuition

Initialize ans = n, low = 0, high = n - 1. While low <= high: calculate mid. If arr[mid] > x, record ans = mid and move left (high = mid - 1). Else (arr[mid] <= x), move right (low = mid + 1). Return ans.

When to apply: Industry standard optimal solution for upper bound and strict range queries.

Algorithm

  1. Step 1: Initialize low = 0, high = arr.length - 1, and ans = arr.length.
  2. Step 2: Enter while loop with condition low <= high.
  3. Step 3: Compute mid = low + (high - low) / 2 safely.
  4. Step 4: If arr[mid] > x: update ans = mid and move left (high = mid - 1).
  5. Step 5: Else (arr[mid] <= x): move right (low = mid + 1).
  6. Step 6: Return ans.

Upper Bound Search Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Initialize low = 0, high = 9, ans = 10
Visual state
Values and pointers at this exact step
array
S
2
3
6
7
8
8
11
11
11
12
0
↑ low
1
2
3
4
↑ mid
5
6
7
8
9
↑ high
Variables at this step
low
0
high
9
mid
4
midVal
8
ans
10
Check / comparison
arr[mid] = 8 > x = 11 -> FALSE (8 <= 11)
Decision / next transition
8 is not strictly greater than 11. Search right: low = mid + 1 = 5.
Why this step matters

Initialize low = 0, high = 9, ans = 10. Calculate mid = 0 + (9 - 0) / 2 = 4. arr[4] = 8.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int upperBound(const vector<int>& arr, int x) {
7 int low = 0, high = (int)arr.size() - 1;
8 int ans = arr.size();
9
10 while (low <= high) {
11 int mid = low + (high - low) / 2;
12
13 if (arr[mid] > x) {
14 ans = mid; // Candidate strictly greater element found
15 high = mid - 1; // Search left for smaller satisfying index
16 } else {
17 low = mid + 1; // Search right
18 }
19 }
20 return ans;
21}
22
23int main() {
24 vector<int> arr = {2, 3, 6, 7, 8, 8, 11, 11, 11, 12};
25 int x = 11;
26 cout << "Upper Bound index of " << x << " is: " << upperBound(arr, x) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval in O(log N) iterations.
  • Space complexity: O(1) — Uses constant O(1) auxiliary variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear ScanO(N)O(1)Scan array from left to right for first arr[i] > x.Linear scan
2.Recursive Upper BoundO(log N)O(log N)Divide and conquer recursion.Call stack
3.Iterative Binary SearchOptimalO(log N)O(1)Halve search space, recording mid and searching left whenever arr[mid] > x.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using >= instead of > (turns it into Lower Bound instead of Upper Bound).

Pitfall 2:

Searching right on arr[mid] > x instead of searching left.

Crucial Edge Cases to Validate:

  • Target Larger than or Equal to All Elements: arr = [1, 3, 5], x = 5 -> returns 3 (n).
  • Target Smaller than All Elements: arr = [4, 6, 8], x = 1 -> returns 0.
  • Multiple Duplicate Elements: arr = [2, 2, 2, 2], x = 2 -> returns 4 (n).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain how [lower_bound(x), upper_bound(x) - 1] defines the complete half-open range of x in sorted data.
  2. Show how range query problems like count occurrences and equal range rely on upper bound.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.For array arr = [1, 2, 2, 2, 5] and x = 2, what will lower_bound and upper_bound return?

2.If all elements in arr are <= x, what does upperBound(arr, x) return?

Back to DSA Sheet