題目

  • 題目連結
  • 目標函式 : search(nums, target)
    • Input : nums: List[int]、target: int
    • Output : int

解題概念

  • 題意 : 給予按升序排序的整數陣列 nums 和一整數 target
  • 如果target存在 nums 中，則返回其 index value，不然回傳 -1
  • 時間複雜度要求 : $\color{DB4D6D}{O(\log(n))}$

我的寫法

  • 想法 : 這題就是標準的 Binary Search 題型，我這裡使用了 Iteration 的寫法
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def search(self, nums, target):
        
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] > target: # target 位於 nums[left] 與 nums[mid] 之間
                right = mid - 1
            else: # target 位於 nums[mid] 與 nums[right] 之間
                left = mid + 1
            
        return -1
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(\log(n))}$
    • Runtime: 205 ms (faster than 64.40%)
    • Memory Usage: 14.4 MB (more than 90.68%)

解答 or 其他優秀寫法 - Recursion 版本

  • 想法 : 此為 Binary Search 的另一種寫法
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def search(self, nums, target):
        
        def binarySearch(left, right):
            if left <= right : 
                mid = (left + right) // 2

                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    return binarySearch(left, mid - 1)
                else:
                    return binarySearch(mid + 1, right)

            return -1
            
        l = 0
        r = len(nums) - 1
        return binarySearch(l, r)
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(\log(n))}$
    • Runtime: 219 ms (faster than 7.83%)
    • Memory Usage: 20.6 MB (more than 7.34%)