704. Binary Search

# Approach. Binary Search
# Time Complexity: O(log n)
# Space Complexity: O(1)
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return -1
        left_index = 0
        right_index = len(nums) - 1
        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2
            if nums[middle_index] < target:     # right part
                left_index = middle_index + 1
            elif nums[middle_index] > target:   # left part
                right_index = middle_index - 1
            else:   # found
                return middle_index

        return -1

Notes:

程式流程

• 因為題目中提到nums是一個遞增陣列，所以可以用binary search 找到解 (如果存在)，而binary search 的 time complexity為 O(log n)
• Pseudo-code

  left_index = 0 # 初始化左邊的index
  right_index = length - 1 # 初始化右邊的index (因為array的index 0開始，所以right_index為長度減1)
  while left_index <= right_index : # 跑迴圈，直到 left_index > right_index離開，表示沒找到target
      middle_index = (left + right) // 2
      middle = nums[middle_index)
      若中間值(middle)小於target -> target在右半邊， left_index = middle_index + 1
      若中間值(middle)大於target -> target在左半邊， right_index = middle_index -1
      若前兩個條件都不成立，表示middle等於target -> 找到target，return middle_index
  若離開while loop都沒回傳結果，表示沒找到target，return -1

紀錄

• 5分鐘 ： 了解題目 (assumptions、work through examples, function signature)
• 2-3分鐘 ： 考慮brute force solution (O(n))，已知陣列是遞增且排序，不可能用暴力解法，所以並未實作，並根據題目給的條件，應該用binary search的方式實作(O(log n))
• 15分鐘寫下pseudo code，並轉成Python code，舉幾個例子用手寫(模擬)的方式跑過一次程式碼
• 5分鐘：把手寫的程式碼輸入Leetcode並執行

備註

• 在第一次模擬程式執行過程中，發現我的第一版程式有bug，while loop的條件應該是 left <= right，但是我寫成left < right
• 難度上來說，介於過於簡單跟難度適中之間，因為第一版有bug，表示我一開始並未考慮到所有情況，所以選擇難度適中