34. Find First and Last Position of Element in Sorted Array

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.

規則

尋找已排序過的陣列找到 first 和 last target 數

測試案例

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

思路

  1. 透過已排序過的輸入，透過二元搜尋法切割查找
  2. 找到 first 和 last，回傳 index
  3. 如果沒找到則回傳 -1

實作

nums = [1, 3, 3, 5, 7, 8, 9, 9, 9, 15]
target = 9
print(Solution().searchRange(nums, target))
# [6, 8]

測試進入點:

def getRange(self, arr, target):
    first = self.binarySearch(arr, 0, len(arr) - 1, target, True)
    last = self.binarySearch(arr, 0, len(arr) - 1, target, False)
    return [first, last]

二元搜尋法切割查找

def binarySearch(self, nums, low, high, target, findFirst):
# 如果查到底都沒有則返回 -1
    if high < low:
        return -1

取中間位數

mid = low + (high - low) // 2 # 取得中間位數

接下來開始判斷是否取得 first or last

if findFirst:

核心條件判斷:

# first: mid = 0 or 目標大於中間數左邊 +++ 目標=中間數 => 符合條件
if (mid == 0 or target > nums[mid - 1]) and target == nums[mid]:
    return mid

規則一: 如果目標大於中間數 -> 在右邊 -> low + 1 往右邊推移 -> 重新計算中間數

if target > nums[mid]:
    return self.binarySearch(nums, mid + 1, high, target, findFirst)

規則二: 如果目標小於中間數 -> 在左邊 -> high - 1 往左邊推移 -> 重新計算中間數

return self.binarySearch(nums, low, mid - 1, target, findFirst)

依照上列做法就可以先取得 first 數，其實就是不斷的改變關注點並且調整區域取得中間數。 last 則是從後面開始進行 binary search:

 # last: mid = 陣列長度 or 目標小於中間數右邊 +++ 目標=中間數 => 符合條件      
 if (mid == len(nums) - 1 or target < nums[mid + 1]) and target == nums[mid]:
    return mid

規則一: 如果目標小於中間數 -> 在左邊 -> high - 1 往左邊推移 -> 重新計算中間數

 if target < nums[mid]:
    return self.binarySearch(nums, low, mid - 1, target, findFirst)

規則二: 如果目標大於中間數 → 在右邊 -> low + 1 往右邊推移 -> 重新計算中間數

return self.binarySearch(nums, mid + 1, high, target, findFirst)

第一個解法就完成了

完整代碼

def binarySearch(self, nums, low, high, target, findFirst):
    if high < low:
        return -1
    mid = low +(high-low)//2
    if findFirst:
        if (mid == 0 or target > nums[mid - 1]) and target == nums[mid]:
            return mid
        if target > nums[mid]:
            return self.binarySearch(nums, mid + 1, high, target, findFirst)
        else: 
            return self.binarySearch(nums, low, mid - 1, target, findFirst)
    else:
        if (mid == len(nums) - 1 or target < nums[mid + 1]) and target == nums[mid]:
            return mid
        if target < nums[mid]:
            return self.binarySearch(nums, low, mid-1, target, findFirst)
        else:
            return self.binarySearch(nums, mid + 1, high, target, findFirst)

另一種解法

透過觀察可以看到一但符合條件開始要重新計算中間數時，這邊要做的就是改變觀點跟定位去取得新的區域並且重新計算中間數再來判斷(binary search) 那麼有沒有辦法可以讓代碼更簡潔並具有可讀性?

def binarySearchIterative(self, nums, low, high, target, findFirst):

這邊要創造一個 while 來不斷地輪查數字，用於取代 recursion，並且將原本改變候傳入的基準點給予變數:

if findFirst:
    #...
    if (target > nums[mid]):
        low = mid + 1
    else:
        high = mid - 1
else:
    #...
    if (target < nums[mid]):
        high = mid - 1
    else:
        low = mid + 1

完整代碼

def binarySearchIterative(self, nums, low, high, target, findFirst):
    while True:
    if high < low:
        return -1
    
    mid = low +(high-low)//2
    if findFirst:
        if (mid == 0 or target > nums[mid - 1]) and target == nums[mid]:
            return mid
        if (target > nums[mid]):
            low = mid + 1
        else:
            high = mid - 1
    else:
        if (mid == len(nums)-1 or target < nums[mid + 1]) and target == nums[mid]:
            return mid
        if (target < nums[mid]):
            high = mid - 1
        else:
            low = mid + 1