Log inSign up
easyGeeksforGeeksNot Started

Lower 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 Lower Bound of x.

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

You must implement a solution in O(log n) time.

Example 1 · Exact Element Present with Duplicates:

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

Example 2 · Element Absent but Fallback Exists:

Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 5
Output: 2
Explanation: The smallest index with arr[i] >= 5 is index 2 (arr[2] = 8).

Example 3 · All Elements Smaller than x:

Input: arr = [1, 2, 3, 4], x = 9
Output: 4
Explanation: All elements are < 9, so lower bound is index 4 (arr.length).

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:

  • Master the Lower Bound binary search invariant (arr[mid] >= x).
  • Understand why high = mid - 1 is needed to find the smallest satisfying index.
  • Learn how C++ std::lower_bound works under the hood.

Pattern Recognition Trigger

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

Signals to Look For:

  • Find smallest index where condition arr[i] >= x holds
  • Finding start of equal/greater elements range
  • Sorted array with duplicates

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1, ans = n.
  • Compute 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:

Upper BoundSearch Insert PositionFirst Occurrence of ElementFloor and Ceiling

1. Linear Scan

Intuition

Loop through the array starting from index 0. Check if (arr[i] >= x) return i;. If loop completes without finding any element >= 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 no such element exists, return arr.length.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int lowerBound(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 = {1, 2, 8, 10, 10, 12, 19};
15 cout << "Linear Lower Bound for 10: " << lowerBound(arr, 10) << endl;
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(N) — Worst case scans all N elements when all values are less than x.
  • Space complexity: O(1) — Uses a single loop index variable.

2. Recursive Lower Bound

Intuition

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

When to apply: Recursive divide and conquer implementations.

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 lowerBound(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 = {1, 2, 8, 10, 10, 12, 19};
21 cout << "Recursive Lower Bound: " << lowerBound(arr, 10) << endl;
22 return 0;
23}

Time & Space Complexity

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

3. Iterative Binary Search Lower Bound (Gold Standard)

Intuition

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

When to apply: Industry standard optimal solution for lower bound and range search 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.

Lower Bound Search Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initialize low = 0, high = 6, ans = 7
Visual state
Values and pointers at this exact step
array
S
1
2
8
10
10
12
19
0
↑ low
1
2
3
↑ mid
4
5
6
↑ high
Variables at this step
low
0
high
6
mid
3
midVal
10
ans
3
Check / comparison
arr[mid] = 10 >= x = 10 -> TRUE
Decision / next transition
Record ans = 3. Search left to check if smaller index exists: high = mid - 1 = 2.
Why this step matters

Initialize low = 0, high = 6, ans = 7. Calculate mid = 0 + (6 - 0) / 2 = 3. arr[3] = 10.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int lowerBound(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 answer found
15 high = mid - 1; // Look for smaller index on the left
16 } else {
17 low = mid + 1; // Must look on the right
18 }
19 }
20 return ans;
21}
22
23int main() {
24 vector<int> arr = {1, 2, 8, 10, 10, 12, 19};
25 int x = 10;
26 cout << "Lower Bound index of " << x << " is: " << lowerBound(arr, x) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval at each step in log2(N) iterations.
  • Space complexity: O(1) — Requires O(1) auxiliary pointer 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 from left to right for first arr[i] >= x.Linear iteration
2.Recursive Lower 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.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Searching right after finding arr[mid] >= x instead of searching left.

Pitfall 2:

Initializing ans = -1 instead of ans = n.

Crucial Edge Cases to Validate:

  • Target Exceeds All Elements: arr = [1, 3, 5], x = 10 -> returns 3 (n).
  • Target Smaller than All Elements: arr = [4, 6, 8], x = 1 -> returns 0.
  • Multiple Duplicate Values: arr = [2, 2, 2, 2], x = 2 -> returns 0 (first occurrence).

Interview Tips & Best Practices

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

  1. Mention that std::lower_bound in C++ returns an iterator to the exact position calculated here.
  2. Show how upper_bound(x) - lower_bound(x) gives the exact frequency count of x in O(log N) time.

Quick Comprehension Check

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

1.What is the difference between Lower Bound and Upper Bound in C++ / DSA?

2.If all elements in arr are strictly smaller than x, what should lowerBound(arr, x) return?

Back to DSA Sheet