Implementing Lower Bound Search

In our last lesson, we established a robust template for finding an exact value in a sorted array using binary search. This gave us a powerful tool for achieving $O(\log n)$ performance, but its application was limited to finding a single, specific item. Today, we'll generalize this powerful algorithm to solve a much broader and more common class of problems.

Our goal is to implement a "lower-bound" search. Instead of asking, "Does this exact value exist?", we will ask, "What is the first position in this array that satisfies a given ordered condition?" Mastering this pattern is a significant step toward overcoming algorithm anxiety, as it provides a reliable structure for problems that don't immediately look like simple searches.

Beyond Exact Matches: Monotonic Conditions

The binary search from our previous lesson works beautifully for finding an exact target. But what happens if the target appears multiple times? For example, in [2, 5, 5, 5, 8, 10], which 5 would our algorithm find? The answer is: we don't know. It depends on the sequence of mid pointers.

To handle this and many other problems, we need to reframe our thinking. Instead of searching for a value, let's search for a boundary. The key insight is that for any sorted array, we can define a condition that creates a monotonic sequence of boolean values.

For example, consider the condition value >= 5 applied to the array above. The result is:

[F, T, T, T, T, T] (where F is False, T is True)

This structure, a series of False values followed by a series of True values, is the foundation for a more general binary search.

The AlgoMonster article "Binary Search and Monotonic Function" explains this concept well.

Our new goal is no longer to find a specific value, but to find the index of the first True in such a conceptual boolean array. This is what "lower-bound search" means.

Adapting the Binary Search Template

How do we modify our trusted binary search template to find this boundary? Let's start with an intuitive modification for the specific problem of finding the first occurrence of a number.

The mycodeschool channel has an excellent video that builds directly on the standard binary search you've already learned. When a match is found, instead of stopping, it records the position and continues searching to the left for an even earlier match.

This video provides the crucial intuition. Now, let's formalize this into a more general and robust template that works for any monotonic condition, not just arr[mid] === target.

Our new template will explicitly track the best answer found so far.

1. Initialize a variable, let's call it boundary_index, to a default value like -1.
2. Use the same while (left <= right) loop.
3. Inside the loop, check if mid satisfies our condition (i.e., if it's "feasible" or True).
   • If feasible(mid) is True: This is a potential answer! We record it (boundary_index = mid) and then try to find an even better (earlier) answer by continuing our search in the left half: right = mid - 1.
   • If feasible(mid) is False: The answer must be in the right half, so we discard the left side: left = mid + 1.
4. After the loop finishes, boundary_index will hold the index of the first True, or -1 if none were found.

This image perfectly illustrates the logic for the True case:

A Complete Implementation

Let's apply this template to a classic interview problem: LeetCode 34. Find First and Last Position of Element in Sorted Array. Finding the "first position" is a perfect application of lower-bound search.

The monotonic condition here is nums[mid] >= target.

The AlgoMonster resource on this problem provides a clean template and a full TypeScript implementation.

Here is the core logic from that resource, adapted into a standalone function for finding the lower bound:

/**
 * Finds the index of the first element in a sorted array
 * that is greater than or equal to the target.
 * @returns The index of the first element >= target, or array length if all are smaller.
 */
function findLowerBound(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    let boundary_index = nums.length; // Default to length if not found

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] >= target) {
            // This is a potential answer. Store it and look for an earlier one.
            boundary_index = mid;
            right = mid - 1;
        } else {
            // The answer must be to the right.
            left = mid + 1;
        }
    }
    return boundary_index;
}

Note on the default value: In this implementation, if no element is greater than or equal to the target, the loop will finish and the function will return nums.length. This is a common and useful convention, as it represents the position where the target would be inserted to maintain the sorted order.

For a final conceptual walkthrough, the NeetCode video explains this strategy using the term "left bias," which is another helpful way to think about it.

Conclusion

In this lesson, we elevated our understanding of binary search from a simple tool for finding exact values to a powerful technique for solving a wide range of boundary-finding problems.

Here are the key takeaways:

• Monotonicity is Key: Binary search can be applied to any problem that can be modeled as a monotonic boolean function (e.g., ...FFFFTTTT...).
• Search for the Boundary: Lower-bound search is about finding the first element that satisfies a condition, which is equivalent to finding the boundary between False and True.
• The Lower-Bound Template: When mid is a potential solution, you store it (boundary_index = mid) and continue searching for a better one in the "earlier" half (right = mid - 1). If mid is not a solution, you must search in the "later" half (left = mid + 1).

You now have two powerful binary search templates in your toolkit. In our next lesson, we will complete the set by learning "upper-bound" search. This variant finds the first element strictly greater than a target, and when combined with the lower-bound search we learned today, it allows you to solve many problems related to ranges and counts in sorted data.