1 題目

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(log n) 的算法解決此問題。

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例 2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一個(gè)非遞減數(shù)組
• -109 <= target <= 109

2 解答

二分查找，這里用的是閉區(qū)間

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        ans = []
        left = 0
        right = n-1

        while left <= right:
            mid = (left + right)//2
            middle = nums[mid]
            if middle >= target: # right 的右邊一定的大于等于target
                right = mid - 1
            elif middle < target: # left的左邊一定小于target
                left = mid + 1
        ans.append(left)
        if left == n or nums[left] != target:
            return [-1 , -1]

        left = 0
        right = n-1
        while left <= right:
            mid = (left + right) // 2
            middle = nums[mid]
            if middle > target: # right的右邊一定大于target
                right = mid -1
            elif middle <= target: # left的左邊一定小于等于target
                left = mid +1
        ans.append(right)
        return ans