今天是紀錄LeetCode解題的第三十四天

第三十四題題目：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.

給定一個按升序排列的整數數組nums，找到target在nums中第一次和最後一次出現的索引，如果沒有找到則回傳[-1,-1]，時間複雜度須為O(log n)

解題思路

這題和上一題33題同樣都是用二分搜尋法，先設left = 0、right = len(nums) - 1和欲搜尋的index = -1，一樣算出中點mid，判斷target落在左半邊還是右半邊來縮減邊界，如果找到索引值的話，第一個出現的索引值要繼續往左邊尋找(縮減右邊界)看還有沒有更早出現的索引，最後一個出現的索引值則相反要繼續往右尋找(縮減左邊界)

程式碼

class Solution:
    def searchRange(self, nums, target):
        def findIndex(nums, target, FirstOrLast):
            left, right = 0, len(nums) - 1
            index = -1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1left
                elif nums[mid] > target:
                    right = mid - 1
                elif nums[mid] == target:
                    index = mid
                    if FirstOrLast == "First":
                        right = mid - 1 #繼續往左找
                    elif FirstOrLast == "Last":
                        left = mid + 1  #繼續往右找
            return index
        return [findIndex(nums, target, "First"), findIndex(nums, target, "Last")]

執行過程

初始狀態

• nums = [1,2,3,2,5,2,2]
• target = 2
• left = 0
• right = 6
• index = -1

找第一個位置(第一次執行)

• mid = (left + right) // 2 = (0 + 6) // 2 = 3
• nums[mid] == target → nums[mid] = nums[3] = 2 == target = 2 → True
• index = mid = 3
• right = mid - 1 = 2

找第一個位置(第二次執行)

• mid = (left + right) // 2 = (0 + 2) // 2 = 1
• nums[mid] == target → nums[mid] = nums[1] = 2 == target = 2 → True
• index = mid = 1
• right = mid - 1 = 0

找第一個位置(第三次執行)

• mid = (left + right) // 2 = (0 + 0) // 2 = 0
• nums[mid] < target → 1 < 2
• left = mid + 1 = 1
• left <= right → False → return index = 1

找最後一個位置(第一次執行)

• mid = (left + right) // 2 = (0 + 6) // 2 = 3
• nums[mid] == target → nums[mid] = nums[3] = 2 == target = 2 → True
• index = mid = 3
• left = mid + 1 = 4

找最後一個位置(第二次執行)

• mid = (left + right) // 2 = (4 + 6) // 2 = 5
• nums[mid] == target → nums[mid] = nums[5] = 2 == target = 2 → True
• index = mid = 5
• left = mid + 1 = 6

找最後一個位置(第三次執行)

• mid = (left + right) // 2 = (6 + 6) // 2 = 6
• nums[mid] == target → nums[mid] = nums[6] = 2 == target = 2 → True
• index = mid = 6
• left = mid + 1 = 7
• left <= right → False → return index = 6

最後回傳答案[1,6]
相信大家做了那麼多的二分搜尋的題目都和筆者一樣越來越會寫程式囉~