攝影：産品經理 繼續跟産品經理吃大餐
在使用 Python 的時候，如果要判斷一個字元串是否在另一個包含字元串的清單中，可以使用
in
關鍵詞，例如：
'pm',
但是，Golang 是沒有
in
這個關鍵詞的，是以如果要判斷一個字元串數組中是否包含一個特定的字元串，就需要一個一個對比：
package main
運作效果如下圖所示：
但這種方式有一個弊端，就是要周遊整個字元串數組。如果數組裡面有100萬條資料，那麼平均要周遊50萬次才能找到。這是一個非常費時間的操作。
有沒有什麼辦法可以優化這個操作呢？
如果是有序的整型數組，那麼我們可以使用二分查找，把時間複雜度
O(n)
降到對數時間複雜度。字元串能不能也這樣操作呢？實際上是可以的。
在 Golang 中，有一個排序子產品
sort
，它裡面有一個
sort.Strings()
函數，可以對字元串數組進行排序。同時，還有一個sort.SearchStrings()[1]函數，會用二分法在一個有序字元串數組中尋找特定字元串的索引。
結合兩個函數，我們可以實作一個更高效的算法：
package main
運作效果如下圖所示：
其中，
sort.Strings
是一個 in-place 的修改方式，是直接修改的
str_array
。修改以後
str_array
變成有序的字元串數組。接下來通過二分查找快速定位。如果找到了，那麼傳回目标字元串在排序後的清單中第一次出現的索引。如果沒有找到，那麼傳回數組中最後一個元素的索引。是以隻要 index 小于最後一個元素的索引，那麼目标字元串肯定存在；如果等于最後一個元素的索引，但是值不等于最後一個元素，那麼目标字元串就不存在于字元串數組中。
通過先排序再查詢的方式，對于100萬個元素的字元串數組，隻需要查詢20次左右就能确認字元串是否存在。速度大大提升。
最後考大家一個思考題。
name_list
一開始是亂序的字元串數組，在上圖第23行，如果列印一下
name_list
，列印出來的是經過排序的，還是沒有經過排序的字元串數字？
參考資料
[1]
sort.SearchStrings()
: https://golang.org/pkg/sort/#SearchStrings