Go中的二進制搜索算法

功效

• 時間：O（log n），這是最差的對數
• 空間：0(1)，需要持續的時間

執行

``````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">&gt;=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> &lt; len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&amp;&amp;</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`

``````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
}``````

``````a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6``````

• `i``0``j``9`
• `h`計算為`(0 + (9-0) / 2)`=`4`
• `a[h]``15`。這意味著我們執行`j = h`

• `i``0``j``4`
• `h`計算為`(0 + (4-0) / 2)`=`2`
• `a[h]``6`。我們找到了`x`，這意味著我們返回`h = 2`

搜索逆序

``````a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6``````

``i := sort.Search(len(a), func(i int) bool { return a[i] <= x })``