# Binary search: take a sortcut [sic]

yourbasic.org/golang
Binary search is faster than linear search, but only works if your data is in order. It's a sortcut. Dan Bentley

You might be able to use one of the three custom binary search functions: `sort.SearchInts`, `sort.SearchStrings` or `sort.SearchFloat64s`.

They all have the signature

``func SearchType(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``````

There is also a 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 slice.