Find First and Last Position: Boundary Binary Search Pattern

Learning Outcome

After this lesson, you should be able to use lower-bound style binary search to find left and right boundaries.

Problem Statement

Given a sorted array and a target, return the first and last index of target, or [-1,-1] if target is absent.

Brute Force Approach

Linearly scan to find the first and last target. This can take O(n).

Optimized Approach

Run binary search for the first index >= target and the first index > target. The right boundary is one before the second result.

Exact Pseudocode

left = lowerBound(target)
rightExclusive = upperBound(target)
if left is out of range or nums[left] != target:
  return [-1, -1]
return [left, rightExclusive - 1]

lowerBound(x):
  find first index where nums[index] >= x
upperBound(x):
  find first index where nums[index] > x
  

Reference Code

class Solution:
    def searchRange(self, nums, target):
        def first_ge(x):
            l, r = 0, len(nums)
            while l < r:
                m = (l + r) // 2
                if nums[m] < x:
                    l = m + 1
                else:
                    r = m
            return l

        def first_gt(x):
            l, r = 0, len(nums)
            while l < r:
                m = (l + r) // 2
                if nums[m] <= x:
                    l = m + 1
                else:
                    r = m
            return l

        left = first_ge(target)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        return [left, first_gt(target) - 1]
  

Sample Dry Run

Complexity

Edge Cases

• Empty array returns [-1,-1].
• All values equal target should return the whole range.
• Avoid target + 1 overflow by using upper_bound logic.

Interview Checklist

• Use half-open range [l, r) for clean boundaries.
• Validate target exists after finding left.
• Use upper bound for the right boundary.

FAQs