如何在Go中實現二進制搜索算法
二元搜尋是一種簡單的算法,可以在排序數組,並且通常被稱為學習新的編程語言時要學習的代碼示例。
功效
這非常有效:
- 時間:O(log n),這是最差的對數
- 空間:0(1),需要持續的時間
理論
給定一個已排序的數組,我們在中間選擇項Y,然後將其與目標值X進行比較。
如果Y與X匹配,則返回Y位置,然後退出。
我們確定是否X <Y,在這種情況下,我們丟棄右側,然後移至左側的中間,並重複與上述相同的操作。
當Y最終與X匹配時,搜索結束。如果這沒有發生,我們將返回X在數組中所處的位置。
執行
幸運的是,Go標準庫在其標準庫中提供了一個二叉樹實現sort
包裝,在sort.Search()
。
讓我們來看看API的用法(如包裝文檔中所述),因此我們知道sort.Search
應該返回:
package main
import (
“fmt”
“sort”
)
func main() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
<span style="color:#a6e22e">i</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">sort</span>.<span style="color:#a6e22e">Search</span>(len(<span style="color:#a6e22e">a</span>), <span style="color:#66d9ef">func</span>(<span style="color:#a6e22e">i</span> <span style="color:#66d9ef">int</span>) <span style="color:#66d9ef">bool</span> { <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">>=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> < len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&&</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">==</span> <span style="color:#a6e22e">x</span> {
<span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"found %d at index %d in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">i</span>, <span style="color:#a6e22e">a</span>)
} <span style="color:#66d9ef">else</span> {
<span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"%d not found in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">a</span>)
}
}
sort.Search
返回索引i
,而我們只需要確保該索引實際上包含x
。
當然,我們想知道它是如何在內部實現的。由於標準庫是用Go語言和開源語言編寫的,因此很容易看到sort.Search
實現:
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 := i + (j-i)/2 // 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
}
讓我們分解一下:
給定一個具有長度的數組n
,以及比較功能f
(內部評估x >= a[h]
),我們開始迭代數組a
。
讓我們使用示例中使用的實際值,可以更輕鬆地顯示正在發生的事情。
數據:
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
迭代1:
i
是0
,j
是9
。h
計算為(0 + (9-0) / 2)
=4
a[h]
是15
。這意味著我們執行j = h
迭代2:
i
是0
,j
是4
。h
計算為(0 + (4-0) / 2)
=2
a[h]
是6
。我們找到了x
,這意味著我們返回h = 2
搜索逆序
由於我們可以將函數傳遞給sort.Search
,很容易搜索以相反順序排序的數組,例如
a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6
通過傳遞一個比較的函數a[i] <= x
代替a[i] >= x
。
i := sort.Search(len(a), func(i int) bool { return a[i] <= x })
更多教程:
- 使用NGINX反向代理服務Go服務
- 在Go中復制結構
- Go Web服務器的基礎
- 在Go中對地圖類型進行排序
- 簡而言之去指針
- 轉到標籤說明
- 開始日期和時間格式
- 使用Go進行JSON處理
- 可變參數函數
- 去弦備忘單
- 轉到空界面說明
- 使用VS Code和Delve調試Go
- 命名為Go返回參數
- 在Go中生成隨機數和字符串
- Go項目的文件系統結構
- Go中的二進制搜索算法
- 在Go中使用命令行標誌
- GOPATH解釋
- 使用Go構建一個命令行應用程序:lolcat
- 使用Go構建CLI命令:Cowsay
- 在Go中使用殼管
- Go CLI教程:財富克隆
- 使用Go列出文件夾中的文件
- 使用Go從GitHub獲取存儲庫列表
- 去,將一小段字符串附加到文件中
- 去,將字符串轉換為字節片
- 使用Go可視化您本地的Git貢獻
- Go CPU和內存分析入門
- 解決Go程序中的“不支持索引”錯誤
- 測量Go程序中的執行時間
- 使用Go構建Web爬網程序以檢測重複的標題
- 最佳實踐:指針還是價值接收者?
- 最佳實踐:您應該使用方法還是函數?
- Go數據結構:集
- 前往地圖備忘單
- 在Go中生成泛型類型的實現
- Go數據結構:字典
- Go數據結構:哈希表
- 在“通過通道”中實現事件偵聽器
- Go數據結構:堆棧
- Go數據結構:隊列
- Go數據結構:二進制搜索樹
- Go數據結構:圖形
- Go數據結構:鍊錶
- Go數據結構的完整指南
- 比較Go值
- Go是面向對象的嗎?
- 在Go中使用SQL數據庫
- 在Go中使用環境變量
- 上篇教程:PostgreSQL支持的REST API
- 在Go Web服務器上啟用CORS
- 在Docker容器中部署Go應用程序
- 為什麼Go是作為PHP開發人員學習的功能強大的語言
- 去,刪除io.Reader.ReadString換行符
- 開始,如何觀看更改並重建程序
- 去算一下自約會以來的月份
- 在Go中訪問HTTP POST參數