二分搜索

二分搜索是一個非常適合面試的題型，因為這個題型有幾個特點

1. 模板存在，題目變化多元，細節實作是魔鬼
2. 實作所需花費的時間合理
3. 考察到應試者對於各種邊界情況的觀察
4. 應試者需要多與面試者溝通對於實作的細節

基本二分搜索

先從 704. Binary Search 作為開始，題目給定一個「元素不重複」的有序陣列，以及一個目標值，求目標值的索引為何？目標不一定存在。

這裡不展開二分搜索的演算法是什麼，先透過答案來看二分搜索的架構。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            num = nums[mid]
            if num > target:
                right = mid - 1
            elif num < target:
                left = mid + 1
            else:
                return mid
        
        return -1

實作邏輯非常的簡單，但是在進去其他的題目之前，要很清楚的熟悉幾個問題

left = 0, right = len(nums) - 1 的意義為何？

這個的意義代表著我們今天要搜尋的區間為 [0, len(nums) - 1]

while left <= right 的意義為何？

二分搜索是透過每次縮小一半的搜尋區間來加速搜尋的過程，最後會在某一個點，沒有更小的搜索區間了。

如果是 while left < right 很好理解，代表左邊界跟右邊界之間一定還有元素，我們要繼續縮小搜尋區間，但是為什麼要加入等號？這裡有兩個情況可以考慮，在快要結束二分搜索之前，有可能會有兩種情況，一種是搜尋空間剩下兩個元素，一個是搜尋空間剩下三個元素。