• Leetcode 34
• Difficulty: Medium
• Patterns:
  • Binary Search

---

Problem Definition

Given an array of numbers sorted in non-decreasing order, find the first and last position of a target value in the array. If the target is not found, return [-1, -1].

---

Examples

Some test cases to verify our solution.

assert(find_first_last([0, 0, 0, 1, 1, 2, 2, 2, 3], 5) == (-1, -1))
assert(find_first_last([0, 0, 0, 1, 1, 2, 2, 2, 3], 1) == (3, 4))
assert(find_first_last([0, 0, 0, 1, 1, 2, 2, 2, 3, 6, 7], 5) == (-1, -1))
assert(find_first_last([1, 2, 3, 4, 5], 4) == (3, 3))
assert(find_first_last([1, 3, 4, 5, 5, 5, 6], 5) == (3, 5))
assert(find_first_last([1], 1) == (0, 0))
assert(find_first_last([2, 2], 2) == (0, 1))
assert(find_first_last([1, 2, 3], 1) == (0, 0))

---

Single Binary Search Solution

We implement a binary search to find an occurrence of target and then traverse left to find the first and right to find the last position of target in the array.

def find_first_last(nums: list[int], target: int) -> tuple[int, int]:
    n = len(nums)
    l, r = 0, n - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            first = mid
            last = mid
            while first > 0 and nums[first - 1] == target:
                first -= 1
            while last < n - 1 and nums[last + 1] == target:
                last += 1
            return (first, last)
        elif l == r:
            break
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid
    return (-1, -1)

---

Single Binary Search Solution Complexity

Let $n = $ len(nums).

In the worst case, we might traverse the whole string because every number is the target. So runtime complexity should be $O(n)$. However, on average, the runtime should be $O(log(n))$.

Auxiliary space complexity should be $\Theta(1)$.

---

Single Binary Search Solution

We can implement a double binary search to find both ends. This should be better in $O$ runtime.

def find_first_last(nums: list[int], target: int) -> tuple[int, int]:
    n = len(nums)
    l, r = 0, n - 1
    while l <= r:
        mid = (l + r) // 2
        # Find the left boundary
        if nums[mid] == target and (mid == 0 or nums[mid - 1] != target):
            if mid == n - 1:
                return (mid, mid)
            first = mid
            left, right = mid, n - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target and (mid == n - 1 or nums[mid + 1] != target):
                    return (first, mid)
                elif nums[mid] == target:
                    left = mid + 1
                else:
                    right = mid
        elif l == r:
            break
        elif nums[mid] >= target:
            r = mid
        else:
            l = mid + 1
    return (-1, -1)

---

Single Binary Search Solution Complexity

Let $n = $ len(nums).

Since we're doing 2 nested binary searches but running each search exactly once, the runtime complexity should be $O(log(n))$.

Auxiliary space complexity should be $\Theta(1)$.