本篇要來介紹 LeetCode 超常見的主題 Binary Search，中文就是 二分搜尋演算法，以往我們在查找陣列的某一個值的時候，最直覺的做法是一個一個從陣列索引值 0 到 n，一個一個確認是不是題目要的數值，最糟的情況剛好數值在陣列最後一個，這樣會導致時間複雜度為 O(n)，而二分搜尋法正好可以讓搜尋更有效率，就讓我們看下去吧！

二分搜尋法介紹

一個已經排序好的陣列，利用持續切半的方式尋找數值，就是二分搜尋法，它能夠把時間複雜度減少到只有 O(logn)，在實踐的過程，我們會宣告三個參數分別記錄當下的索引查找狀態，分別是 left 左邊索引值，right 右邊索引值，mid 中間切一半的索引值。雖然這題概念很簡單好懂，但它在寫程式的時候最難的地方是邊界條件的判斷能不能寫對，如果沒寫好不小心就會 Out of Index，也就是超出陣列索引值之外而拋出例外錯誤，所以寫 LeetCode 題目時務必要小心。

舉個例子，假設一個排列好順序的陣列如下：

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

目標要查找數字 7，並且要知道它的索引位置在 3。

暴力搜尋

此時暴力搜尋會是如下程式碼，會在陣列第一個查找到最後一個。

func linearSearch(nums: [Int], target: Int) -> Int? {
    for (index, num) in nums.enumerated() {
        if num == target {
            return index
        }
    }
    return nil
}

也叫做線性搜尋法，這就是剛才提到的會導致時間複雜度為 O(n)。

二分搜尋

那麼用二分搜尋法的做法會是：

var left = 0
var right = nums.count - 1

宣告left 和 right，left 在陣列索引值 0，而 right 在陣列的最尾端。

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
 ^                               ^
left                            right

再來就是切半獲得 mid 中間索引值，會用 (left + right) / 2計算出結果。這裡是 Swift 語言就不用擔心會溢位問題，可以左右相加再除二。

let mid = (left + right) / 2

這樣 mid 擺在陣列就會長這樣。

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
 ^           ^                   ^
left        mid                 right

抓出 9 後發現它比我們要的 7 結果還要大，所以需要往切半的左邊查找。

因此 right 會移動到 mid -1 的位置。

 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
  ^  ^     ^
left mid   right

再來算出 mid 位置，用一樣的公式 (0+3)/2 獲得 1 的位置。

發現 mid 等於 3，比 7 還要小，因此往切半的右邊繼續查找。

所以 left 會移動到 mid + 1的位置。

 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
        ^  ^
      left right

再來計算 mid 則是 (2+3)/2=2，發現 mid 等於 5 還是小於 7，所以 left 繼續移動 mid + 1=3。

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
          ^
       left&right

此時左右都重疊了，算出 mid = (3+3)/2=3，索引值 3 取出 7 就是我們要的結果可以返回。

請注意這是左閉右閉的陣列查找法，所以判斷迴圈繼續的條件是 left <= right。

如果是左閉右開，意思是 right 一開始會在陣列之外，那又是不一樣的迴圈判斷了，詳細參照網路其他資料，這裡就不贅述。

最終 Swift 程式碼出來了！其實它是 LeetCode 704. Binary Search 題目，在學習的過程我們做完了一個題目。

func binarySearch(nums: [Int], target: Int) -> Int? {
    var left = 0
    var right = nums.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        
        if nums[mid] == target {
            return mid
        }
        else if nums[mid] < target {
            left = mid + 1
        }
        else {
            right = mid - 1
        }
    }
    
    return nil
}

// 範例使用
let sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
let targetValue = 7

if let result = binarySearch(nums: sortedArray, target: targetValue) {
    print("目標值 \(targetValue) 在索引 \(result) 的位置")
} else {
    print("找不到目標值 \(targetValue)")
}

總結

這個演算法看似很簡單，但是在剛開始練習時會常常算不好索引值，所以還是不能小看題目變化的時候能不能好好掌握題目，最終寫出正確答案，還是需要經過一陣思考梳理出答案，而且最重要的是要注意它是不是排序好的陣列，如果不是這個查找方式就會無用了，所以要多多注意。