# Binary search in Go

yourbasic.org/golang

Use one of the **binary search** functions: `sort.SearchInts`

, `sort.SearchFloat64s`

or `sort.SearchStrings`

.

They all have the signature

`func Search`**Type**(a []**Type**, x **Type**) int

and return

- the smallest index
`i`

at which`x <= a[i]`

, or `len(a)`

if there is no such index.

The slice must be sorted in **ascending order**.

```
a := []string{"A", "C", "C"}
fmt.Println(sort.SearchStrings(a, "A")) // 0
fmt.Println(sort.SearchStrings(a, "B")) // 1
fmt.Println(sort.SearchStrings(a, "C")) // 1
fmt.Println(sort.SearchStrings(a, "D")) // 3
```

## Generic binary search

Use the **generic binary search** function `sort.Search`

.

```
func Search(n int, f func(int) bool) int
```

It returns

- the smallest index
`i`

at which`f(i)`

is true, - or
`n`

if there is no such index.

It requires that `f`

is false for some (possibly empty) prefix
of the input range and then true for the remainder.

This example mirrors the one above, but uses the generic `sort.Search`

instead of `sort.SearchInts`

.

```
a := []string{"A", "C", "C"}
x := "C"
i := sort.Search(len(a), func(i int) bool { return x <= a[i] })
if i < len(a) && a[i] == x {
fmt.Printf("Found %s at index %d in %v.\n", x, i, a)
} else {
fmt.Printf("Did not find %s in %v.\n", x, a)
}
// Output: Found C at index 1 in [A C C].
```

## Time complexity

Binary search runs in worst-case logarithmic time, making *O*(log *n*) comparisons, where *n* is the size of the array.