介紹二分搜尋法的應用

題目連結: 34. Find First and Last Position of Element in Sorted Array

題目描述:給定一個已按照非遞減順序排列的整數陣列 nums，以及一個目標值 target。如果 target 存在於陣列中，請找出它的起始位置和結束位置。如果 target 不存在，則返回 [-1, -1]。

注意:此題要求時間複雜度必須是 O(log n)。

Python

這題因為時間複雜度的關係明確地指向了二分搜尋。但是，標準的二分搜尋只能告訴我們 target 是否存在，或者找到其中任意一個 target 的位置，無法直接告訴我們它的範圍。

因此，我們的策略是：執行兩次二分搜尋，一次用來尋找左邊界，另一次用來尋找右邊界。

def bs(nums:List[int],target:int) ->List[int]:
    left =0
    right = len(nums)-1
    while left <= right:
        mid = (left+right)//2
        if nums[mid] < target:
            left = mid +1
        else:
            right = mid -1
    return left

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = bs(nums,target)
        end = bs(nums,target+1)-1
        if start == len(nums) or nums[start] != target:
            return [-1,-1]
        else:
            return [start,end]
        
                

演算法分析:

• 先理解bs這個二分搜尋的函式，最後回傳的left是陣列中第一個大於或等於 target 的元素的索引。
• if nums[mid] < target這一行表示如果中間值比 target 小，那麼 target 的插入點一定在右邊，所以 left = mid + 1。，這就是為何left會是第一個大於或等於 target 的元素的索引。
• start是題目所要尋找的左邊界，end則是右邊界，值得注意的是，bs(nums, target + 1) 代表著函式會返回第一個大於或等於 target + 1 的元素的索引。
• 如果我們找到了第一個比 target 還要大的元素的位置，那麼這個位置的前一個 (-1)，不就正好是 target 出現的最後一個位置嗎？
• 所以最後會-1
• 例如:nums = [5, 7, 7, 8, 8, 10], target = 8，end的值會返回元素10的位置，最後再減去1就是所求。
• left會一直向右移動，直到等於陣列長度則代表沒有找到target這個值，返回[-1,-1]。
• 或者 target 根本就不存在，返回[-1,-1]。

複雜度分析:
* 每一次執行bs函式的時間複雜度都是 O(log n)，所以時間複雜度為 O(log n)。
* 空間複雜度為O(1)。

今天就介紹到這邊，有問題都可以留言
下回見!