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

要求

給定一個按照升序排列的整數陣列 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]

```

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