Hands-On High Performance with Go

Binary search

A much more commonly used pattern (and the pattern that you'd most likely want to use for a performant search algorithm) is called binary search. An implementation of a binary search algorithm can be found in the Go standard library at https://golang.org/src/sort/search.go and was displayed in the sort search function earlier in this chapter. A binary search tree has an O(log n) search complexity compared to the O(n) complexity of the linear search function that we wrote previously. Binary search tends to get used frequently, especially when the dataset that needs to be searched gets to any sort of reasonable size. Binary search is also smart to implement early – if the dataset that you have grows without you being privy to ...