Binary Search is a simple algorithm to find an item in an sorted array, and it’s usually referenced as a code sample to study when learning a new programming language.
Efficency
It’s very efficient:
- Time: O(log n), it’s at worst logaritmic
- Space: 0(1), takes constant time
Theory
Given a sorted array, we pick the item Y in the middle and we compare it to the target value X.
If Y matches X, we return the Y position and we exit.
We determine if X < Y, in this case we discard the right side, and we go in the middle of the left side, and we repeat the same operation as above.
The search ends when Y finally matches X. If this does not happen, we return the position that X would have taken if it was in the array.
Implementation
We’re lucky, the Go standard library provides a binary tree implementation in its sort
package, in sort.Search()
.
Let’s see the usage of the API, as taken from the package documentation, so we know what sort.Search
should return:
package main
import (
"fmt"
"sort"
)
func main() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
i := sort.Search(len(a), func(i int) bool { return a[i] >= x })
if i < len(a) && a[i] == x {
fmt.Printf("found %d at index %d in %v\n", x, i, a)
} else {
fmt.Printf("%d not found in %v\n", x, a)
}
}
sort.Search
returns an index i
, and we just need to make sure that that index actually contains x
.
Of course we want to know how this is implemented internally. Since the standard library is written in Go, and open source, it’s really easy to see how sort.Search
is implemented:
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
}
Let’s break it down:
Given an array with length n
, and a comparison function f
(that internally evaluates x >= a[h]
), we start iterating the array a
.
Let’s use the actual values we use in the example, it’s easier to show what’s happening.
Data:
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
Iteration 1:
i
is0
,j
is9
.h
is calculated as(0 + (9-0) / 2)
=4
a[h]
is15
. This means we executej = h
Iteration 2:
i
is0
,j
is4
.h
is calculated as(0 + (4-0) / 2)
=2
a[h]
is6
. We found the position ofx
, this means we returnh = 2
Searching reverse order
Since we can pass a function to sort.Search
, it’s easy to search on an array sorted in the reverse order, like
a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6
by passing a function that compares a[i] <= x
instead of a[i] >= x
.
i := sort.Search(len(a), func(i int) bool { return a[i] <= x })