Lower & upper bound
In one line
Lower bound finds the first index whose value is >= target and upper bound finds the first index whose value is > target, which gives first and last positions, counts and insert points in O(log n).
What it is
Classic binary search stops as soon as it finds any copy of the target. With duplicates, or when the target is missing, you often need a boundary instead: where does the block of equal values start, where does it end, or where would a new value be inserted to keep the array sorted?
Lower bound returns the first index i where nums[i] >= target. Upper bound returns the first index i where nums[i] > target. Both return n (one past the end) if no such index exists. In Python these are bisect.bisect_left and bisect.bisect_right; in C++ they are std::lower_bound and std::upper_bound.
Everything else follows: the target exists if lower bound < n and nums[lower bound] == target; its last position is upper bound - 1; the number of copies is upper bound - lower bound.
Why interviewers ask
Most real binary search questions are boundary questions: first bad version, first and last position of an element, insert position, count of values in a range. Interviewers want to see that you can pick a range convention and update rule that never skips the boundary and never loops forever. Getting this template right once makes every later binary search problem easier.
How it works
- 1Use a half-open range: lo = 0, hi = n. The answer is always in [lo, hi], and hi = n means 'not found, insert at the end'.
- 2While lo < hi, compute mid = (lo + hi) // 2. Since mid < hi, mid is always a valid index.
- 3For lower bound, ask 'is nums[mid] < target?'. If yes, mid and everything left of it are too small, so lo = mid + 1. If no, mid might be the first valid index, so keep it: hi = mid.
- 4For upper bound, ask 'is nums[mid] <= target?' instead. Everything else is identical.
- 5The loop ends when lo == hi; that single index is the boundary. Each step shrinks the range because lo = mid + 1 moves right and hi = mid moves left of the old hi.
- 6Think of it as finding the first true in a sequence of false, false, true, true: the condition for lower bound is nums[i] >= target.
Worked example · Bounds of 2 in [1, 2, 2, 2, 3, 5]
- Lower bound: lo = 0, hi = 6. mid = 3, nums[3] = 2, not < 2, so hi = 3.
- lo = 0, hi = 3. mid = 1, nums[1] = 2, not < 2, so hi = 1.
- lo = 0, hi = 1. mid = 0, nums[0] = 1 < 2, so lo = 1. Now lo == hi == 1: lower bound is 1.
- Upper bound: lo = 0, hi = 6. mid = 3, nums[3] = 2 <= 2, so lo = 4. mid = 5, nums[5] = 5 > 2, so hi = 5. mid = 4, nums[4] = 3 > 2, so hi = 4. lo == hi == 4: upper bound is 4.
- So 2 occupies indexes 1 to 3 (last = 4 - 1), and appears 4 - 1 = 3 times. For target 4, both bounds are 5: the count is 0 and 4 would be inserted at index 5.
Picture it
A shelf of books sorted by author. Lower bound is where the first book by 'Smith' starts; upper bound is the spot right after the last 'Smith'. If there is no Smith, both point to the same gap: exactly where a Smith book would be shelved.
Reference code
def lower_bound(nums, target):
"""First index i with nums[i] >= target (len(nums) if none)."""
lo, hi = 0, len(nums) # half-open range [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < target:
lo = mid + 1 # mid is too small, answer is right of it
else:
hi = mid # mid could be the answer, keep it
return lo
def upper_bound(nums, target):
"""First index i with nums[i] > target (len(nums) if none)."""
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def count_of(nums, target):
return upper_bound(nums, target) - lower_bound(nums, target)
The half-open range [lo, hi) always contains the answer, including n for 'past the end'. hi = mid keeps a possible answer; lo = mid + 1 drops one that is too small. The two functions differ only in < versus <=. Each is O(log n) time and O(1) space.
Key patterns
First and last position
When: Find the start and end of a block of duplicates
How: start = lower_bound(target); end = upper_bound(target) - 1; check start < n and nums[start] == target first.
Search insert position
When: Where would a value go to keep the array sorted
How: Return lower_bound(target); it is n when the value is larger than everything.
First true / first bad version
When: A predicate is false then true over indexes
How: Same template: if predicate(mid) then hi = mid else lo = mid + 1; the answer is lo.
Count in range
When: How many values are in [a, b]
How: upper_bound(b) - lower_bound(a), in O(log n) for each query.
Closest value
When: Find the element nearest to x
How: i = lower_bound(x); compare nums[i - 1] and nums[i] (when they exist) and pick the closer one.
Real-world use
Python bisect and C++ std::lower_bound
bisect.bisect_left, bisect.bisect_right and bisect.insort are used to keep lists sorted and to look up ranges; C++ std::lower_bound and std::upper_bound power std::equal_range and sorted-vector containers.
Range queries in databases
For WHERE created_at BETWEEN a AND b, a B-tree index finds the first key >= a (a lower bound), then reads entries in order until it passes b, so it never touches rows outside the range.
LSM-tree storage engines
RocksDB and LevelDB keep sorted keys in SSTable files; to serve a Get or start a range scan they binary search the index block for the first entry whose key is >= the lookup key.
Time-series and log lookups
Monitoring and logging tools keep samples sorted by timestamp; a dashboard query for 10:00 to 11:00 uses a lower bound on 10:00 and an upper bound on 11:00 to slice exactly the needed samples.
In a project
An e-commerce price filter must show how many of 500,000 products cost between 20 and 50 dollars, updating instantly as the user drags a slider.
- Keep a sorted array of all product prices, rebuilt when the catalogue changes.
- For a range [low, high], compute lower_bound(prices, low) and upper_bound(prices, high).
- The count is upper - lower, and the products at those indexes are exactly the matching ones, already sorted by price.
- Unit test boundaries: a price exactly equal to low or high, a range with no products, and ranges past either end.
Impact: Each slider move costs about 2 x 19 comparisons instead of scanning 500,000 prices, so the count updates within a frame and the filter feels instant even on a phone.
Trade-offs
Use it when
- The array has duplicates and you need the first, last or count
- You need the insert position of a value
- You answer many range or nearest-value queries on static sorted data
Avoid it when
- Data changes often: inserting into a sorted array is O(n); use a balanced BST or a sorted container instead
- You only need exact existence of a key: a hash set is simpler and O(1) on average
- The data is not sorted by the key you are querying
Cost: O(log n) per bound, O(1) extra space. Count in range is two bounds, still O(log n).
Common mistakes
- Stopping on the first equal element when the question asks for the first or last occurrence, which gives O(log n) only by luck and a wrong index otherwise.
- Finding one match and then scanning left and right, which becomes O(n) when there are many duplicates.
- Mixing hi = n - 1 with the half-open template, so the answer n (insert at end) can never be returned.
- Using lo = mid instead of lo = mid + 1, which loops forever when hi = lo + 1.
- Forgetting to check that lower_bound < n and nums[lower_bound] == target before saying the value exists.
Interview questions
Quick revision
- lower_bound: first i with nums[i] >= target. upper_bound: first i with nums[i] > target.
- Half-open template: lo = 0, hi = n, while lo < hi, hi = mid or lo = mid + 1.
- Lower bound tests nums[mid] < target; upper bound tests nums[mid] <= target.
- Count of target = upper - lower. Last index = upper - 1.
- Missing target: lower == upper == insert position.
- Python: bisect_left, bisect_right. C++: std::lower_bound, std::upper_bound.
- Any false-then-true predicate uses the same template (first bad version).
Check yourself
1. For nums = [1, 3, 3, 3, 7] and target 3, what are lower_bound and upper_bound?
2. What does lower_bound return for target 10 in [2, 4, 6]?
3. In the half-open template, why is hi = mid used instead of hi = mid - 1 when nums[mid] >= target?
4. Which expression counts the elements of a sorted array in [a, b]?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.