34. Find First and Last Position of Element in Sorted Array

by Aaron • 3/9/2025, 8:55:42 AM

Description

Medium

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Solution

當然可以簡單的 scan 整個 array 來找到 target 的起始和結束位置，但是這樣的時間複雜度是 O(n)。我們可以使用 binary search 來解決這個問題，我們可以先找到 target 的起始位置，然後再找到 target 的結束位置。這樣的時間複雜度是 O(log n)。

分成兩個部分：

找到最左邊：如果 mid 的值等於 target，我們就將 mid 設為結束位置，然後繼續往左邊找，直到找到最左邊的位置。
找到最右邊: 如果 mid 的值等於 target，我們就將 mid 設為起始位置，然後繼續往右邊找，直到找到最右邊的位置。

ruby

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def search_range(nums, target)
    range_start = binary_search(nums, target) do |mid, left, right|
        [mid, left, mid - 1]
    end

    range_end = binary_search(nums, target) do |mid, left, right|
        [mid, mid + 1, right]
    end
    [range_start, range_end]
end

def binary_search(nums, target)
    idx = -1
    left = 0
    right = nums.size - 1

    while left <= right
        mid = (left + right) / 2
        if nums[mid] == target
            idx, left, right = yield(mid, left, right)
        elsif nums[mid] > target
            right = mid - 1
        else
            left = mid + 1
        end
    end
    return idx
end

Reference

leetcode