Rust程式語言內建的contains方法可以用來判斷某元素是否在一個陣列或是切片中，而binary_search方法則可以用來尋找某元素在一個已排序的陣列或是切片中出現的索引位置。那麼問題就來了，這兩個方法若都用來判斷某元素在已排序的陣列或是切片中是否存在的話，究竟哪個會比較快呢？



我們先來看看以下程式碼：

fn contains_1<T: PartialEq + Ord>(a: &[T], x: &T) -> bool {
    a.contains(x)
}

fn contains_2<T: PartialEq + Ord>(a: &[T], x: &T) -> bool {
    a.binary_search(x).is_ok()
}

以上程式，contains_1和contains_2函數的功能都是判斷一個元素是否在一個切片中，分別用Rust程式語言內建的contains方法和binary_search方法來實作。

使用contains_1函數所呼叫的contains方法是使用線性搜尋的方式來實作的，所以它的最差時間複雜度為#{{O(n)}}#；使用contains_2函數所呼叫的binary_search方法是使用二元搜尋的方式來實作的，所以它的最差時間複雜度為#{{O(\log{n})}}#，其所傳入的切片必須要是一個已排序好的切片。

這樣看起來，對於一個已排序好的切片使用contains_2函數來判斷切片是否有某元素，似乎是會比使用contains_1函數還好對吧？

效能實測

直接實際寫一段程式來測試運算效能吧！這段程式可以在GitHub上取得：

https://github.com/magiclen/rust-performance-measurement/blob/master/benches/contains_binary_search.rs

根據測試結果，可以發現binary_search方法並不一定都比contains方法快。以char型別的切片來說，切片長度在大約32以上時，使用binary_search方法的效能才會比contains方法好。這個長度臨界值通常會根據元素互相比較大小的複雜程度而有所變動，比較的複雜度愈高，binary_search方法的優勢就愈明顯。