leetcode_34 在排序陣列中查詢元素的第一個和最後一個位置

語言: CN / TW / HK

要求

給定一個按照升序排列的整數陣列 nums,和一個目標值 target。找出給定目標值在陣列中的開始位置和結束位置。

如果陣列中不存在目標值 target,返回 [-1, -1]。

進階:

你可以設計並實現時間複雜度為 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 是一個非遞減陣列
  • -109 <= target <= 109

核心程式碼

```python class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: lo,hi = 0,len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: break elif nums[mid] > target: hi = mid - 1 else: lo = mid + 1 if lo > hi: return [-1,-1]

    midtarget = mid
    lo,hi = 0,mid
    leftpos = 0
    while lo <= hi:
        if (hi >= 1 and nums[hi - 1] != target) or hi == 0:
            leftpos = hi
            break
        mid = (lo + hi) // 2
        if nums[mid] == target:
            hi = mid
        elif nums[mid] < target:
            lo = mid + 1

    rightpos = 0    
    lo,hi = midtarget,len(nums) - 1

    while lo <= hi:
        if (lo <= len(nums) - 2 and nums[lo + 1] != target) or lo == len(nums) - 1:
            rightpos = lo
            break
        mid = (lo + hi + 1) // 2
        if nums[mid] == target:
            lo = mid
        elif nums[mid] > target:
            hi = mid - 1

    return [leftpos,rightpos]

```

image.png

解題思路:我們使用二分查詢的方式首先先來定位target的位置,若定位不到就直接返回[-1,-1],然後我們定位到了一個target,我們將資料分割成左右兩個部分,在左側我們找左邊界,在右側我們找右邊界,都是使用二分查詢的方式,我們的時間複雜度o(logn)。