Go語言實現二分查詢演算法

二分查詢也稱折半查詢（Binary Search），它是一種效率較高的查詢方法。但是，二分查詢演算法的前提是傳入的序列是有序的（降序或升序），並且有一個目標值。

二分查詢的核心思想是將 n 個元素分成大致相等的兩部分，取中間值 a[n/2] 與 x 做比較，如果 x=a[n/2]，則找到 x，演算法中止，如果 x<a[n/2]，則只要在陣列 a 的左半部分繼續搜尋 x，如果 x>a[n/2]，則只要在陣列 a 的右半部搜尋 x。

二分查詢雖然效能比較優秀，但應用場景也比較有限，底層必須依賴陣列，並且還要求資料是有序的，對於較小規模的資料查詢，我們直接使用順序遍歷就可以了，二分查詢的優勢並不明顯，二分查詢更適合處理靜態資料，也就是沒有頻繁插入、刪除操作的資料。

思路：

1) 先找到中間的下標 middle = (leftIndex + RightIndex) /2 ，然後用中間的下標值和需要查詢的值（ FindVal）比較。

a：如果 arr[middle] > FindVal，那麼就向 LeftIndex ~ (midlle-1) 區間找
b：如果 arr[middle] < FindVal，那麼就向 middle+1 ~ RightIndex 區間找
c：如果 arr[middle] == FindVal，那麼直接返回

2) 從第一步的 a、b、c 遞回執行，直到找到位置。

3) 如果 LeftIndex > RightIndex，則表示找不到，退出。

程式碼/舉例：

定義一個包含（1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97）等值的陣列，假設說要查詢 30 這個值，如果按照回圈的查詢方法，找到 30 這個值要執行 7 次，那麼如果是按照二分查詢呢？二分查詢的過程如下：

left = 1, right = 18; mid = (1+18)/2 = 9; 51 > 30
left = 1, right = mid - 1 = 8; mid = (1+8)/2 = 4; 15 < 30
left = mid + 1 = 5, right = 8; mid = (5+8)/2 = 6; 30 = 30 查詢完畢

如上所示只需要執行 3 次，大大減少了執行時間，具體程式碼實現如下所示：

package main

import (
    "fmt"
)
//二分查詢函數 //假設有序陣列的順序是從小到大（很關鍵，決定左右方向）
func BinaryFind(arr *[]int, leftIndex int, rightIndex int, findVal int)  {
    //判斷 leftIndex是否大於rightIndex
    if leftIndex > rightIndex {
        fmt.Println("找不到")
        return
    }
    //先找到 中間的下標
    middle := (leftIndex + rightIndex) / 2

    if (*arr)[middle] > findVal {
        //要查詢的數，範圍應該在 leftIndex 到 middle+1
        BinaryFind(arr, leftIndex, middle-1, findVal)
    } else if (*arr)[middle] < findVal {
        //要查詢的數，範圍應該在 middle+1 到 rightIndex
        BinaryFind(arr, middle+1, rightIndex, findVal)
    } else {
        fmt.Printf("找到了，下標為：%v n", middle)
    }
}


func main() {
    //定義一個陣列
    arr := []int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97}
    BinaryFind(&arr, 0, len(arr) - 1, 30)
    fmt.Println("main arr=",arr)
}

執行結果如下所示：

D:code>go run main.go
找到了，下標為：6
main arr= [1 2 5 7 15 25 30 36 39 51 67 78 80 82 85 91 92 97]