Skip to content

Instantly share code, notes, and snippets.

@SchumacherFM
Created December 1, 2016 19:21
Show Gist options
  • Save SchumacherFM/f361b404e29889b8bf00378e988ae240 to your computer and use it in GitHub Desktop.
Save SchumacherFM/f361b404e29889b8bf00378e988ae240 to your computer and use it in GitHub Desktop.
Binary Search vs Loop Search
// /usr/local/go-master/libexec/bin/go test -v . -bench ^BenchmarkSearch$ -run ^$
// Loop 20000 68347.0 ns/op 0 B/op 0 allocs/op
// Binary 30000000 47.9 ns/op 0 B/op 0 allocs/op
// PASS
// ok 3.584s
package main_test
func BenchmarkSearch(b *testing.B) {
list := make([]int, 1000000)
for i := range list {
list[i] = i
}
b.Run("Loop", func(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
if x := loopSearch(list, 123456); x != 123456 {
b.Fatalf("Have %d Want %d", x, 123456)
}
}
})
b.Run("Binary", func(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
if x := binarySearch(list, 123456); x != 123456 {
b.Fatalf("Have %d Want %d", x, 123456)
}
}
})
}
func loopSearch(sortedList []int, lookingFor int) int {
for i := 0; i < len(sortedList); i++ {
if sortedList[i] == lookingFor {
return i
}
}
return -1
}
func binarySearch(sortedList []int, lookingFor int) int {
var lo int = 0
var hi int = len(sortedList) - 1
for lo <= hi {
var mid int = lo + (hi-lo)/2
var midValue int = sortedList[mid]
if midValue == lookingFor {
return mid
} else if midValue > lookingFor {
// We want to use the left half of our list
hi = mid - 1
} else {
// We want to use the right half of our list
lo = mid + 1
}
}
// If we get here we tried to look at an invalid sub-list
// which means the number isn't in our list.
return -1
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment