PPractick

The problem

An online store keeps product prices sorted, and its "filter from ₹X upwards" feature needs the first position whose price is at least X; everything from there onward matches the filter. That position is the lower bound of X. It's the most useful variant of binary search, because it answers existence (is a[lb] == x?), insertion position, first occurrence and counting questions. Unlike plain binary search, it always returns a position, which is n if every element is smaller than X.

Example: [3, 5, 8, 15, 19], X = 9 → 3 (the first price ≥ 9 is 15, at index 3).

Function signature

int lowerBound(const vector<int>& a, int x);  // smallest index i with a[i] >= x, or n if none

Test cases

Input (a, x)	Output	Explanation
([1, 2, 2, 3], 2)	1	The first 2
([3, 5, 8, 15, 19], 9)	3	15 is the first value ≥ 9
([3, 5, 8, 15, 19], 20)	5	Every value is smaller: return n
([3, 5, 8, 15, 19], 1)	0	Every value is ≥ 1
([1, 2, 2, 3], 3)	3
([], 4)	0	Empty array: n = 0

(Confirm: the array is sorted non-decreasingly and may contain duplicates; the result matches std::lower_bound.)

How interviewers phrase it

• "Find the lower bound of X in a sorted array" (Coding Ninjas).
• Hidden inside many problems: search insert position, first occurrence, floor and ceil, counting occurrences.

Clarifying questions to ask

1. What should be returned if every element is smaller than X: n or -1?
2. Can there be duplicates? (Then "first index ≥ X" matters.)
3. Is the array sorted non-decreasingly?

Follow-ups to expect

1. "How is this different from plain binary search?"
2. "How do you get the first occurrence of X?"
3. "What's the library function?"
4. "How does the half-open-range version look?"
5. "Complexity?"

Related questions

• Search X in sorted array Easy
• Upper Bound Easy
• Search insert position Easy
• Floor and Ceil in Sorted Array Easy
• Count Occurrences in a Sorted Array Easy
• Kth Missing Positive Number Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in