Go面試中如果這樣寫二分查找！
前言
今天與大家分享一下
Go標準庫sort.Search是如何實現(xiàn)二分查找的，為什么突然想到分享這個函數(shù)呢。起因是這周在刷leetcode的一道題時，需要使用到二分查找，最開始是自己實現(xiàn)了一版，后面就想Go語言標準庫這么全，應該會有這個封裝，果然被我找到了，順便看了一下他是怎么實現(xiàn)的，感覺挺有意思的，就趕緊來分享一下。
什么是二分查找
以下來自百度百科：
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。
總結一下，使用二分查找必須要符合兩個要求：
必須采用順序存儲結構 必須按關鍵字大小有序排列
我們來舉個例子，就很容易理解了，就拿我和我女朋友的聊天內容做個例子吧：
我家寶寶每次買一件新衣服，就會習慣性的問我一句，小松子，來猜一猜我這次花了多少錢？
小松子：50？
臭寶：你埋汰我呢？欠打！
小松子：500？
臭寶：你當我是富婆呢？能不能有點智商！
小松子：250？
臭寶：我感覺你在罵我，可我還沒有證據。少啦，少啦！?。?/p>
小松子：哎呀，好難猜呀，290？
臭寶：啊！你這臭男人，就是在罵我！氣死啦，氣死啦！多啦，多啦！
小松子：難道是260？
臭寶：哎呦，挺厲害呀，竟然猜對了！
后面對話內容就省略啦.....
這里我只需要5次就成功猜出來了，這就是二分查找的思想，每一次猜測，我們都選取一段整數(shù)范圍的中位數(shù)，根據條件幫我們逐步縮小范圍，每一次都以讓剩下的選擇范圍縮小一半，效率提高。
二分查找的時間復雜度
二分查找每次把搜索區(qū)域減少一半，時間復雜度為O(logn)。（n代表集合中元素的個數(shù)）。
空間復雜度為O(1)。
自己實現(xiàn)一個二分查找
二分算法的實現(xiàn)還是比較簡單的，可以分兩種方式實現(xiàn)：遞歸和非遞歸方式實現(xiàn)，示例代碼如下：
非遞歸方式實現(xiàn)：
// 二分查找非遞歸實現(xiàn)
func binarySearch(target int64, nums []int64) int {
left := 0
right := len(nums) - 1
for left <= right {
mid := left + (right - left) / 2
if target == nums[mid] {
return mid
}
if target > nums[mid] {
left = mid + 1
continue
}
if target < nums[mid] {
right = mid - 1
continue
}
}
return -1
}
總體思路很簡單，每次我們都選取一段整數(shù)范圍的中位數(shù)，然后根據條件讓剩下的選擇范圍縮小一半。這里有一個要注意的點就是我們在獲取中位數(shù)時使用的寫法是mid := left + (right - left) / 2，而不是mid = （left +right）/2的寫法，這是因為后者有可能會造成位數(shù)的溢出，也就會導致結果出問題。
遞歸方式實現(xiàn)：
func Search(nums []int64, target int64) int {
return binarySearchRecursive(target, nums, 0, len(nums))
}
func binarySearchRecursive(target int64, nums []int64, left, right int) int {
if left > right {
return -1
}
mid := left + (right - left) / 2
if target == nums[mid] {
return mid
}
if nums[mid] < target {
return binarySearchRecursive(target, nums, mid+1, right)
}
if nums[mid] > target {
return binarySearchRecursive(target, nums, left, mid-1)
}
return -1
}
Go標準庫是如何實現(xiàn)二分查找的？
我們先看一下標準庫中的代碼實現(xiàn)：
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
初一看，與我們上面的實現(xiàn)一點也不同呢，我們來分析一下。
入參n就是代表要查找序列的長度，入參f就是我們自定義的條件。這段代碼很短，大概思路就是：
定義好這段序列的開始、結尾的位置 使用位移操作獲取中位數(shù)，這樣能更好的避免溢出 然后根據我們傳入的條件判斷是否符合條件，逐漸縮小范圍
這段代碼與我實現(xiàn)的不同在于，它并不是在用戶傳入的比較函數(shù)f返回true就結束查找，而是繼續(xù)在當前[i, j)區(qū)間的前半段查找，并且，當f為false時，也不比較當前元素與要查找的元素的大小關系，而是直接在后半段查找。所以for循環(huán)退出的唯一條件就是i>=j，如果我們這樣使用，就會出現(xiàn)問題：
func main() {
nums := []int64{1, 2, 3, 4, 5, 6, 7}
fmt.Println(sort.Search(len(nums), func(i int) bool{
return nums[i] == 1
}))
}
運行結果竟然是7，而不是1，如果我們把條件改成return nums[i] >=1，運行結果就對了。這是因為我們傳入的條件并不是讓用戶確認目標條件，這里的思想是讓我們逐步縮小范圍，通過這個條件，我們每次都可以縮小范圍，說的有點饒，就上面的代碼舉個例子?，F(xiàn)在是一個升序數(shù)組，我們要找的數(shù)值是1，我們傳入的條件是return nums[i]>=1，第一進入函數(shù)Search，我們獲取中的中位數(shù)h是3，當前元素是大于目標數(shù)值的，所以我們只能在前半段查找，就是這樣不斷縮小范圍，找到我們最終的那個數(shù)值，如果當前序列中沒有我們要找的目標數(shù)值，那么就會返回我們可以插入的位置，也就是最后一位元素的坐標+1的位置。
這個邏輯說實話，我也是第一次接觸，仔細思考了一下，這種實現(xiàn)還是有一些優(yōu)點的：
使用移位操作，避免因為 i+j太大而造成的溢出如果我們查找序列中有多個元素相等時，且我們要找的元素就是這個時，我們總會找到下標最小的那個元素 如果我們沒找到要找的目標元素時，返回的下標是我們可插入的位置，我們在進行數(shù)據插入時，依然可以保證數(shù)據的有序
注意：使用sort.Search時，入參條件是根據要查找的序列是升序序列還是降序序列來決定的，如果是升序序列，則傳入的條件應該是>=目標元素值，如果是降序序列，則傳入的條件應該是<=目標元素值
解析int(uint(i+j) >> 1)這段代碼
這里我想單獨解析一下這段代碼，因為很少見，所以可以當作一個知識點記一下。這里使用到的是移位操作，通過向右移動一位，正好可以得到/2的結果。具體什么原因呢，我畫了一個圖，手工畫的，看完你就懂了：
懂了吧，兄弟們！移位實現(xiàn)要比乘除發(fā)的效率高很多，我們在平常開發(fā)中可以使用這種方式來提升效率。
這里還有一個點就是使用uint數(shù)據類型，因為uint的數(shù)據范圍是2^32即0到4294967295。使用uint可以避免因為i+j太大而造成的溢出。
總結
好啦，今天的文章到這里就結束了，最后我想說的是，沒事大家可以專研一下Go標準庫中的一些方法是怎樣實現(xiàn)的，好的思想我們要借鑒過來。如果我們在面試中使用這種方式寫出二分查找，那得到的offer的幾率不就又增加了嘛～。
推薦閱讀