Lower and Upper Bound in Sorted Arrays

Finding lower and upper bounds in sorted arrays is a fundamental binary search problem that appears frequently in FAANG interviews. This solution demonstrates efficient implementation with clear edge case handling and performance considerations.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the input array is sorted, or do we need to handle unsorted arrays?
2. What should we return if the target element is not found in the array? Should it be -1 or a specific index?
3. Can we modify the input array, or must we work with it in-place?
4. What is the expected time complexity for follow-up questions? Should we aim for O(log n) or O(n)?
5. Are there any constraints on the size of the input array (e.g., up to 10^6 elements)?

Restate the pattern or problem type in your own words: The lower/upper bound pattern is a variant of binary search used to find the first occurrence (lower bound) or last occurrence (upper bound) of a target value in a sorted array. It's particularly useful when we need to locate the range of occurrences for a specific element, such as finding all indices where a value appears.

Clarify the signal words and constraint shape that point to it: Key signal words include "sorted array", "find first occurrence", "find last occurrence", "range of elements", and "target value". The constraint shape typically involves a sorted input array where we're searching for a specific element and need to identify its position or range.

Note any assumptions you are making: I'm assuming the input array is sorted, which is a fundamental requirement for applying binary search techniques. I'm also assuming that we're working with integer or comparable elements, and that the array can be accessed via index.

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily suited for static scenarios where the entire dataset is available upfront. It's not ideal for streaming data where elements arrive continuously, as it requires the full sorted dataset to perform efficient searches. For online scenarios, we'd need a different approach like maintaining a balanced search tree or using a more dynamic data structure.

The pattern works best in batch processing contexts where we can leverage the sorted property to achieve logarithmic time complexity for range queries.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern include:

• "Find the first occurrence of..." or "Find the last occurrence of..."
• "Search for a value in a sorted array"
• "Insert position of target element"
• "Range of elements" or "Count of elements in a range"
• "Find the leftmost/rightmost index where condition holds"

This pattern fits better than alternatives like linear search or binary search with post-processing because it directly addresses the need to locate boundaries in sorted data structures. Unlike general binary search, which only finds one occurrence, lower/upper bound techniques specifically target the extremal positions of elements or ranges.

The pattern is particularly effective when:

• Input is sorted (or can be sorted)
• Need to find insertion points or ranges
• Multiple occurrences exist and we need boundary positions
• We want to avoid O(n) linear scans

Variations apply when:

• Input is not sorted (use regular binary search with preprocessing)
• Need to find exact matches vs. boundary positions (use standard binary search)
• Working with unbounded ranges or streams (use sliding window or two-pointer approaches)

The core insight is that in sorted arrays, we can leverage the ordering property to efficiently locate not just any occurrence of a value, but its precise leftmost or rightmost boundary position using modified binary search logic.

This approach works because:

1. Sorted nature guarantees that elements with same value are grouped together
2. Binary search can be adapted to continue searching in the direction of boundary
3. The modified condition arr[mid] >= target for lower bound and arr[mid] > target for upper bound ensures we find the extremal positions

3. Approach Evolution

Interview communication script:

My first instinct is to solve this with a brute force approach by scanning the entire array for each query, but that would be O(n) per query which isn't ideal for multiple queries. Let me think about how to optimize this - I notice that if I can preprocess the array to maintain some sorted structure or use binary search, I can reduce each query to O(log n) time.

The key insight is that once we have a sorted array, we can use binary search to find the first occurrence of a target value or determine where it should be inserted. This gives us O(log n) lookup time for each query after O(n log n) preprocessing.

Let me think about what invariant I need to maintain: the array needs to be sorted so that I can apply binary search. If I'm looking for a lower bound, I want the leftmost position where the element is greater than or equal to the target. For upper bound, I want the leftmost position where the element is strictly greater than the target.

The brute force approach would be to scan through the array linearly for each query, checking if elements match or fall within range. This is O(n) time per query, which becomes problematic when we have many queries or large arrays.

For optimization, I can use binary search on a sorted array. Since the problem asks for bounds, I need to understand the difference: lower bound is the first position where element >= target, upper bound is first position where element > target.

The improved approach uses binary search with proper boundary handling to find these positions efficiently.

Brute-force approach and why it is not ideal: The brute force solution would iterate through the entire array for each query to find the first element that meets our criteria. For lower bound, we'd look for the first element >= target, and for upper bound, we'd look for first element > target. This is O(n) per query, making it inefficient when we have multiple queries or large datasets.

Improved approach and the key optimization: The key optimization is to use binary search on a pre-sorted array. By sorting once in O(n log n) time, we can answer each query in O(log n) time. The binary search maintains the invariant that we're always narrowing down to the correct boundary position.

Final approach with step-by-step reasoning:

1. First, I need to understand that this is about finding insertion points in a sorted array
2. For lower bound: find the first position where element >= target (leftmost insertion point)
3. For upper bound: find the first position where element > target (rightmost insertion point)
4. I'll implement both using binary search with proper boundary handling
5. The algorithm works by maintaining the invariant that our search space always contains the answer
6. For lower bound: when arr[mid] >= target, we move right pointer to mid to preserve potential answers
7. For upper bound: when arr[mid] > target, we move right pointer to mid to preserve potential answers

Important invariants that must hold:

• Left pointer always points to a position where all elements before it are < target (for lower bound) or ≤ target (for upper bound)
• Right pointer always points to a position where all elements from it onward are > target (for lower bound) or ≥ target (for upper bound)
• The search space is always valid and contains the answer at termination
• When left == right, we've found our target position

4. Data Structure Choice

For the lower/upper bound problem, the primary data structure is a sorted array or sorted list, which enables binary search operations.

Primary Data Structures Used

1. Sorted Array/List - The main input structure that supports binary search operations
2. Integer indices - For tracking positions during binary search operations

Why Each Data Structure Is Needed

The sorted array is essential because:

• It enables O(log n) binary search operations to find bounds
• The sorted property allows us to make decisions about which half of the array to search next
• It provides a clear mathematical foundation for the lower/upper bound logic

Integer indices are needed to:

• Track current search boundaries (left and right pointers)
• Maintain the invariant that elements at indices less than lower bound are strictly less than target
• Track the position where insertion would occur for upper bound

Time and Space Impact

Time Complexity:

• Binary search operations: O(log n) for each bound
• Overall: O(log n) for both bounds

Space Complexity:

• O(1) additional space for indices and temporary variables
• O(n) for the input array (not counted in auxiliary space)

Helper Structure

No additional helper structures are needed beyond basic integer indices. The algorithm works directly with the sorted array's indices, maintaining the key invariants through careful pointer manipulation.

The simplicity of using just integer indices makes this approach very memory-efficient while maintaining optimal time complexity. The array itself serves as the primary data structure, with no need for hash tables, stacks, or other complex structures.

5. Algorithm Walkthrough

Let's trace through the algorithm using the example nums = [1, 2, 2, 3, 4, 4, 4, 5], target = 4:

Step 1: Initialize left = 0, right = nums.length - 1 = 7

Step 2: First binary search for lower bound:

• mid = (0 + 7) / 2 = 3, nums[3] = 3 < target = 4
• Since nums[mid] < target, move left = mid + 1 = 4
• Now left = 4, right = 7

Step 3: Continue binary search:

• mid = (4 + 7) / 2 = 5, nums[5] = 4 == target = 4
• Since nums[mid] == target, move right = mid - 1 = 4
• Now left = 4, right = 4

Step 4: Continue binary search:

• mid = (4 + 4) / 2 = 4, nums[4] = 4 == target = 4
• Since nums[mid] == target, move right = mid - 1 = 3
• Now left = 4, right = 3

Step 5: Loop exits because left > right. The lower bound is at index left = 4.

Step 6: Second binary search for upper bound:

• Initialize left = 0, right = nums.length - 1 = 7
• mid = (0 + 7) / 2 = 3, nums[3] = 3 < target = 4
• Move left = mid + 1 = 4
• Now left = 4, right = 7

Step 7: Continue binary search:

• mid = (4 + 7) / 2 = 5, nums[5] = 4 == target = 4
• Since nums[mid] == target, move left = mid + 1 = 6
• Now left = 6, right = 7

Step 8: Continue binary search:

• mid = (6 + 7) / 2 = 6, nums[6] = 4 == target = 4
• Since nums[mid] == target, move left = mid + 1 = 7
• Now left = 7, right = 7

Step 9: Continue binary search:

• mid = (7 + 7) / 2 = 7, nums[7] = 5 > target = 4
• Since nums[mid] > target, move right = mid - 1 = 6
• Now left = 7, right = 6

Step 10: Loop exits because left > right. The upper bound is at index right + 1 = 7.

Final Result: Lower bound index = 4, Upper bound index = 7. Range = [4, 7].

The algorithm correctly identifies that element 4 appears in indices 4 through 7, giving us the range [4, 7]. The key insight is that we maintain invariants: for lower bound, we ensure all elements to the left are strictly less than target; for upper bound, we ensure all elements to the right are strictly greater than target.

graph TD
    A[Start] --> B{nums[mid] < target}
    B -- Yes --> C[left = mid + 1]
    B -- No --> D{nums[mid] > target}
    D -- Yes --> E[right = mid - 1]
    D -- No --> F{nums[mid] == target}
    F -- Yes --> G[right = mid - 1]
    G --> H[Loop until left > right]
    C --> H
    E --> H
    F -- No --> I[left = mid + 1]
    I --> H

6. Java Solution

public class LowerUpperBound {
    
    /**
     * Find the leftmost (lower) bound of target in sorted array
     * Returns index of first occurrence or -1 if not found
     */
    public int lowerBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // Verify that target exists at the found position
        return (left < arr.length && arr[left] == target) ? left : -1;
    }
    
    /**
     * Find the rightmost (upper) bound of target in sorted array
     * Returns index of last occurrence or -1 if not found
     */
    public int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // Verify that target exists at the position before found
        int result = left - 1;
        return (result >= 0 && arr[result] == target) ? result : -1;
    }
    
    /**
     * Find the range [start, end] of target in sorted array
     * Returns [-1, -1] if target not found
     */
    public int[] searchRange(int[] arr, int target) {
        int leftBound = lowerBound(arr, target);
        if (leftBound == -1) {
            return new int[]{-1, -1};
        }
        
        int rightBound = upperBound(arr, target);
        return new int[]{leftBound, rightBound};
    }
}

The solution implements binary search variations to find lower and upper bounds efficiently. The key insight is using the invariant that elements to the left of left are less than target, and elements to the right of right are greater than or equal to target. This allows us to find the exact boundaries in O(log n) time without needing to scan linearly.

7. Complexity Analysis

Time Complexity: O(log n)

The algorithm performs binary search operations to find the lower and upper bounds, each taking O(log n) time. Since these operations are performed sequentially and the array is processed only once, the overall time complexity is O(log n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space for variables like left, right, mid, and result tracking. No additional data structures are created that grow with input size, making the space complexity O(1).

Why These Bounds Are Correct:

The binary search approach guarantees that with each iteration, we eliminate half of the remaining search space. For an array of size n, we need at most log₂(n) iterations to find the target or determine its bounds. The space complexity remains constant because we only maintain a fixed number of integer variables regardless of input size.

Optimality:

This solution is optimal for the static search problem where we need to find exact bounds in a sorted array. The O(log n) time complexity matches the theoretical lower bound for searching in a sorted array, as any comparison-based algorithm must examine at least log₂(n) elements to guarantee correctness. The solution cannot be improved further in terms of asymptotic complexity for this specific problem type.

The algorithm's efficiency stems from leveraging the sorted property of the input array, which allows us to eliminate half the search space at each step rather than scanning the entire array linearly.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with proper bounds checking. The algorithm should return appropriate default values (e.g., 0 for lower bound, array.length for upper bound) when searching in an empty array.
• Single element: Verify that the bounds logic works correctly for arrays with one element. The lower bound of a value equal to the single element should return index 0, and bounds for values outside that range should return appropriate indices.

Duplicate Values and Repeated States

• Duplicate elements: The algorithm must correctly handle arrays with duplicates. For lower bound, it should return the leftmost occurrence of a target value; for upper bound, it should return the index just after the rightmost occurrence.
• All elements are the same: When all elements in the array are identical, lower bound of that value should return 0, and upper bound should return array.length.

Boundary Conditions

• Target value less than all elements: Lower bound should return 0, upper bound should also return 0.
• Target value greater than all elements: Lower bound should return array.length, upper bound should also return array.length.
• Target value exactly matches first/last element: Ensure that the correct boundary index is returned.

Common Implementation Mistakes

• Off-by-one errors in loop conditions: Using left < right vs left <= right can cause infinite loops or incorrect results. The correct condition is left < right.
• Incorrect mid calculation: Using (left + right) / 2 can cause integer overflow for large indices. Use left + (right - left) / 2 instead.
• Wrong return index: Returning left vs right in the final step can cause incorrect bounds. For lower bound, return left; for upper bound, return right.
• Not handling edge cases: Failing to properly handle arrays of size 0 or 1 can lead to incorrect behavior.
• Incorrect boundary logic: Confusing the meaning of "lower bound" (first position where element is ≥ target) vs "upper bound" (first position where element is > target).

9. Alternative Approaches

There are several alternative approaches to solving problems that require lower/upper bound searches, each with different trade-offs:

Linear Search Approach: The most straightforward alternative is to perform a linear search through the array to find the first occurrence of the target value. This approach has O(n) time complexity and is simple to implement but inefficient for large datasets. It's only suitable when the array size is small or when the problem constraints explicitly prohibit binary search.

Binary Search with Manual Bound Tracking: Instead of using built-in library functions, one could implement custom binary search logic to find the leftmost or rightmost occurrence. This approach gives more control over the search process but requires careful implementation to avoid off-by-one errors and boundary condition handling.

Two-Step Binary Search: Rather than finding the exact position, this approach first uses binary search to locate any occurrence of the target, then expands outward to find all occurrences. This is particularly useful when we're interested in ranges rather than just bounds, but it's less efficient than direct bound finding.

HashMap-Based Preprocessing: For scenarios where multiple queries are expected on the same dataset, we could preprocess the array into a HashMap that stores all indices for each value. This allows O(1) query time but increases space complexity to O(n) and requires O(n) preprocessing time.

The chosen solution using Arrays.binarySearch() with careful handling of duplicate elements is optimal for single-query scenarios because it leverages the built-in optimized implementation while maintaining O(log n) time complexity and O(1) space complexity. The alternative approaches may be preferred in specific contexts like when we need to handle streaming data or when multiple queries on the same dataset are expected.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic functionality
        int[] arr1 = {1, 2, 4, 4, 5, 6, 7};
        int target1 = 4;
        // Expected: lowerBound = 2, upperBound = 4
        
        // Test case 2: Target not found
        int[] arr2 = {1, 2, 4, 4, 5, 6, 7};
        int target2 = 3;
        // Expected: lowerBound = 2, upperBound = 2
        
        // Test case 3: All elements same
        int[] arr3 = {5, 5, 5, 5, 5};
        int target3 = 5;
        // Expected: lowerBound = 0, upperBound = 5
        
        // Test case 4: Empty array
        int[] arr4 = {};
        int target4 = 1;
        // Expected: lowerBound = 0, upperBound = 0
        
        // Test case 5: Single element array
        int[] arr5 = {3};
        int target5 = 3;
        // Expected: lowerBound = 0, upperBound = 1
        
        // Test case 6: Target smaller than all elements
        int[] arr6 = {2, 4, 6, 8};
        int target6 = 1;
        // Expected: lowerBound = 0, upperBound = 0
        
        // Test case 7: Target larger than all elements
        int[] arr7 = {2, 4, 6, 8};
        int target7 = 10;
        // Expected: lowerBound = 4, upperBound = 4
        
        // Test case 8: Duplicate elements at boundaries
        int[] arr8 = {1, 2, 2, 2, 3};
        int target8 = 2;
        // Expected: lowerBound = 1, upperBound = 4
    }
}

Sample test cases include:

• Basic functionality with duplicates in middle
• Target not present in array
• All elements identical
• Empty input array
• Single element array
• Target outside array bounds (smaller/larger)
• Duplicates at boundaries

These test cases cover the essential scenarios for lower/upper bound search including edge conditions and boundary behavior.

11. Final Summary

The core idea is to efficiently locate the first or last occurrence of a target value in a sorted array using binary search, achieving O(log n) time complexity by leveraging the sorted property to eliminate half the search space at each step. This solution works because we can modify standard binary search to continue searching in the appropriate direction even after finding a match, ensuring we find the extreme boundary of the target value rather than just any occurrence. The approach is optimal for this problem since we must examine at least log n elements to guarantee finding the boundary in a sorted array, and our solution achieves this theoretical minimum.