Lower & Upper Bound (Variations)

1. Introduction

What are Boundary Binary Searches?

In arrays containing duplicate elements, a standard exact-match search returns an arbitrary matching index. Lower Bound and Upper Bound are variations that locate the precise boundaries of duplicate ranges:

Lower Bound (bisect_left): The first index where the element is greater than or equal to target (arr[idx] >= target).

Upper Bound (bisect_right): The first index where the element is strictly greater than target (arr[idx] > target).

Why study them?

These variants define the insertion points to keep an array sorted. They also allow you to solve range query problems—such as "how many times does key X appear in the array?"—in logarithmic time.

Where is it Used?

C++ Standard Library: std::lower_bound and std::upper_bound algorithms.

Python Standard Library: bisect.bisect_left and bisect.bisect_right modules.

---

2. Mental Model: Finding Insertion Slots

Imagine you have a sorted bookshelf with books arranged by weight: [ 2kg, 4kg, 4kg, 4kg, 6kg ]

You receive a new 4kg book and want to slide it into a slot so the shelf remains sorted:

Lower Bound: You slide the book in before all the existing 4kg books (index 1).

Upper Bound: You slide the book in after all the existing 4kg books (index 4).

---

3. Core Concepts & Implementations

Invariant & Boundary Updates

In boundary searches:

We initialize hi = nums.length (not length - 1). If the target is larger than all elements, the correct insertion point is at the very end of the array.

The loop condition is while (lo < hi). The search terminates when lo == hi.

Lower Bound logic: If arr[mid] >= target, then mid is a candidate, but we want to look for a smaller index. We update hi = mid. Otherwise, we search the right half: lo = mid + 1.

Upper Bound logic: If arr[mid] > target, mid is a candidate. We set hi = mid. Otherwise, lo = mid + 1.

---

4. Visual Trace: Lower Bound vs Upper Bound

Let's trace both bounds for target = 4 on array [2, 4, 4, 4, 6]:

---

5. Real-World Applications

Range Queries: To count the frequency of key X in a sorted array, run both bounds:

Auto-complete Prefixes: Searching for words starting with a prefix pre on an sorted array of strings is equivalent to finding the lower bound for string pre and upper bound for pre + '{'.

---

6. Interview Perspective

How Interviewers Ask This Topic

"Find the first and last position of an element in a sorted array." -> This is a direct application of lower bound and upper bound!

"Search insertion position." -> Directly returns lower bound.

Common Mistakes

> 2. Wrong Upper Bound Invariant: Writing >= target inside an Upper Bound search. Upper bound must use > target strictly.

---

7. Summary

Lower Bound (bisect_left): Finds the first index where arr[i] >= target.

Upper Bound (bisect_right): Finds the first index where arr[i] > target.

Search Range: hi must initialize to array.length to allow insertion at the end index.

Loop Invariant: Loop uses while (lo < hi) and terminates when lo == hi.

---

8. Quiz

Question 1: What is the output of lowerBound and upperBound for target = 10 in array [2, 5, 8]?

Answer: Both return 3. Since 10 is larger than all elements, the loop terminates at index 3 (the length of the array), suggesting that the element should be inserted at the end.

Question 2: How do you find the last occurrence of an element X in a sorted array using lowerBound?

Answer: You can find the first occurrence of X + 1 by executing lowerBound(X + 1). The last occurrence of X is at lowerBound(X + 1) - 1 (assuming X exists in the array).

Question 3: If you use the standard template, what is the value of lo and hi when the loop terminates?

Answer: lo is equal to hi. They point to the exact same insertion index.

Question 4: True or False: upper_bound(target) - lower_bound(target) always returns the count of target in the array.

Answer: True. If the element doesn't exist, both bounds return the same insertion index, making the count 0.

Question 5: Why is it crucial to set hi = nums.length instead of nums.length - 1?

Answer: Because if the target is larger than all elements, it must be inserted at index nums.length. If hi is initialized to nums.length - 1, we can never reach the final index.