algo-binary-search-boundary

Answer

The algorithm uses two binary search passes — one to find the first occurrence and another to find the last occurrence of the target.

// SearchRange returns the first and last index of target in a sorted array.
// Returns [-1, -1] if target is not found.
func SearchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }

    first := findFirst(nums, target)
    if first == -1 {
        return []int{-1, -1}
    }

    last := findLast(nums, target)
    return []int{first, last}
}

// findFirst finds the first occurrence of target using binary search.
func findFirst(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    result := -1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if nums[mid] == target {
            result = mid      // record this position
            hi = mid - 1      // continue searching left
        } else if nums[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return result
}

// findLast finds the last occurrence of target using binary search.
func findLast(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    result := -1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if nums[mid] == target {
            result = mid      // record this position
            lo = mid + 1      // continue searching right
        } else if nums[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return result
}

Key technique: When the target is found at mid, instead of returning immediately, we: - For first occurrence: save mid and move hi = mid - 1 to keep searching left. - For last occurrence: save mid and move lo = mid + 1 to keep searching right.

Standard binary search is O(log n) time and O(1) space — two passes keep it O(log n).