“老弟在嗎，我懷疑Go標準庫中的二分查找有bug！”

“老哥別慌，源碼之前沒有祕密，你坐下聽我吹吹 c++ 的牛逼。。”

下面這段Go代碼，你覺得index的結果是多少？

arr := []int{1, 3, 5, 7}
index := sort.Search(len(arr), func(i int) bool {
    return arr[i] == 3
})

index的結果並不是1，而是4。（額，返回4是什麼鬼，難道不應該找到就返回對應的下標，找不到就返回-1嗎）

我們映象中的二分是這樣的：

while (low <= high) {
    mid := (low + high) / 2
    if arr[mid] < target {
        low = mid + 1
    } else if arr[mid] > target {
        high = mid - 1
    } else {
        return mid
    }
}

標準庫中的sort.Search是這樣的：

func Search(n int, f func(int) bool) int {
    i, j := 0, n
    for i < j {
        h := int(uint(i+j) >> 1)
        if !f(h) {
            i = h + 1
        } else {
            // 並不退出循環
            j = h
        }
    }
    return i
}

乍一看，sort.Search像是個二分查找的實現。

但它並不是用戶傳入的比較函數f返回true就結束查找，而是繼續在當前 [i, j) 區間的前半段查找。

並且，當f爲false時，也不比較當前元素與要查找的元素的大小關係，而是直接在後半段查找。

for循環退出的唯一條件是 i >= j 。

後文爲了方便描述，對名詞做個統一。 target 表示要查找的值，也即上面的3。

我們先貼上正確的用法，接着分析：

index := sort.Search(len(arr), func(i int) bool {
    // return arr[i] == 3
    return arr[i] >= 3
})

函數f並不是讓用戶指定 == target 的規則，而是上層和下層一塊配合：

當前元素 < target，那麼必然當前元素之前的元素也 < target（因爲是升序數組），所以只用在後半段查找。

當前元素 >= target，那麼當前元素之前的元素和target的大小不確定；當前元素之後的元素也必然 > 或者 == target。此時，Search只在前半段找。

你仔細想想，就會發現，這種查找方式有一些好處：

  1. 當有多個元素都等於target時，實際上可以找到下標最小的那個元素
  2. 當target不存在時，返回的下標標識瞭如果要將target插入，插入的位置（插入後依然保持數組有序）
  3. 基於這種編程範式，上層只用提供一個與自身數據類型相關的比較函數

sort.Search返回值的正確食用方式：判斷index在len的範圍內，並且index位置的元素的值又和想要查找的值相等，也即 index < len(arr) && arr[index] == target ，條件滿足則說明找到，返回的是下標，條件不滿足則說明沒找到，返回的是可以插入的位置。

另外，我們上面的例子，數組是升序排序的，如果數組是降序，那麼函數f應該使用 <= 。

另外，sort.Search中還有一個小細節， h := int(uint(i+j) >> 1) ，這裏先轉換成uint相加再取半，可以防止兩個int相加溢出。

算法部分再多說一句，實際上函數f和函數Search是一個完整的算法邏輯，只是API爲了提供抽象，強行將邏輯切割開了，如果你之前沒接觸過這種二分算法的思想，光看Search的實現，不看函數f的實現，確實有點容易搞暈。

好，到這，算法部分講完了，接下來我們來聊聊Go和 c++ 的編程範式，也即它們是如何對數據類型做抽象，提供API的。

sort.Search的函數f可以看成是一個回調函數，它只接收下標參數，而不是接收和類型相關的數組作爲參數，上層提供函數f的實現中，直接使用了外層的數組變量，實際上是使用了Go閉包的特性。

那麼假設我想直接提供面向一些基礎類型的查找函數，不再由上層提供函數f呢？事實上sort包還真提供了：

// - 只需傳入整型切片和target
// - 注意，該函數只能對升序數組做查找
func SearchInts(a []int, x int) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}

func SearchFloat64s(a []float64, x float64) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}
func SearchStrings(a []string, x string) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}

但是，由於函數f的實現需要訪問數組，並且做運算符 >= 的比較，也即必須知道數組的類型，也即提供給上層的函數也必須傳入具體類型的數組，所以sort包提供了三個面向基礎類型的函數，看函數的簽名，只是切片類型不同，裏面的實現是一模一樣的。。

假如是其他基礎類型呢，比如int64，float32等等，對不起，沒有。。想要？繼續 ctrl+cv 。。

另外，由於Go不支持函數重載，所以這三個函數名字不能一樣，必須加後綴。。

sort包還提供給上層另外一種使用方式：

type IntSlice []int
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }

這種方式，方法名倒是相同了，但是參數類型不同，也即簽名依然不一致，所以你也沒法適配同一個 type xxx interface 。。並且，也只給你寫了3個。。

還有一點不得不提，事實上，Go可以基於interface{}，對類型做抽象，提供統一接口，由內部判斷類型。但是這種方式會增加運行時開銷。。

最後，我們去看一眼 c++ 標準庫STL中二分查找的接口設計。 std::binary_search 函數聲明如下： 

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);
                      
template <class ForwardIterator, class T, class Compare>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

可以看到，通過函數重載，提供了兩個函數。

函數重載是語法糖，編譯時會生成不同的函數，只不過對寫代碼的人是無感知的。

我們先看第一個， c++ 通過模板手法，所有支持比較運算符的基礎類型都可以直接使用這個函數。並且非基礎類型也可以通過重載比較運算符的方式，直接使用第一個函數。

模板是在編譯時通過模板和帶有具體類型的使用模板的代碼生成模板對應的具體代碼。

運算符重載，是爲自定義類型添加運算符成員函數，使得自定義類型可以直接使用運算符運算。

而第二個函數，實際上是提供了另一種手段，上層可以指定具體類型的比較函數comp。

無論是代碼量，還是執行效率，個人都更喜歡 c++ 一些~

本文相關的測試代碼： https://github.com/q191201771/naza/blob/master/playground/p4/p4.go

最後，感謝閱讀~

原文鏈接： https://pengrl.com/p/20011/

原文出處： yoko blog ( https://pengrl.com )

原文作者： yoko ( https://github.com/q191201771 )

版權聲明：本文歡迎任何形式轉載，轉載時完整保留本聲明信息（包含原文鏈接、原文出處、原文作者、版權聲明）即可。本文後續所有修改都會第一時間在原始地址更新。

相關文章