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

is`0`

,`j`

is`9`

.`h`

is calculated as`(0 + (9-0) / 2)`

=`4`

`a[h]`

is`15`

. This means we execute`j = h`

Iteration 2:

`i`

is`0`

,`j`

is`4`

.`h`

is calculated as`(0 + (4-0) / 2)`

=`2`

`a[h]`

is`6`

. We found the position of`x`

, this means we return`h = 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 })
```