Skip to content

Instantly share code, notes, and snippets.

@lemire
Created July 12, 2024 00:18
Show Gist options
  • Save lemire/08e58dae9b3042787914266544a72e3c to your computer and use it in GitHub Desktop.
Save lemire/08e58dae9b3042787914266544a72e3c to your computer and use it in GitHub Desktop.
slices.BinarySearch is slow?
package main
import (
"fmt"
"slices"
"testing"
)
var ok bool
func linearSearch(array []uint32, ikey uint32) int {
low := 0
high := len(array) - 1
for ; low <= high; low++ {
val := array[low]
if val == ikey {
return int(low)
}
}
return -1
}
func binarySearch(array []uint32, ikey uint32) int {
low := 0
high := len(array) - 1
for low <= high {
middleIndex := low + (high-low)/2 // avoid overflow
middleValue := array[middleIndex]
if middleValue < ikey {
low = middleIndex + 1
} else if middleValue > ikey {
high = middleIndex - 1
} else {
return int(middleIndex)
}
}
return -int(low + 1)
}
func BenchmarkBinarySearch(b *testing.B) {
arr := []uint32{2, 11, 19, 23, 29, 31, 37, 41, 43, 47, 53, 61, 67, 73, 79}
for i := 0; i < b.N; i++ {
for _, item := range arr {
if _, ok = slices.BinarySearch(arr, item); !ok {
b.Fail()
}
}
}
}
func BenchmarkBah(b *testing.B) {
arr := []uint32{2, 11, 19, 23, 29, 31, 37, 41, 43, 47, 53, 61, 67, 73, 79}
for i := 0; i < b.N; i++ {
for _, item := range arr {
if ok = binarySearch(arr, item) >= 0; !ok {
b.Fail()
}
}
}
}
func BenchmarkLi(b *testing.B) {
arr := []uint32{2, 11, 19, 23, 29, 31, 37, 41, 43, 47, 53, 61, 67, 73, 79}
for i := 0; i < b.N; i++ {
for _, item := range arr {
if ok = linearSearch(arr, item) >= 0; !ok {
b.Fail()
}
}
}
}
func main() {
fmt.Println(testing.Benchmark(BenchmarkLi))
fmt.Println(testing.Benchmark(BenchmarkBah))
fmt.Println(testing.Benchmark(BenchmarkBinarySearch))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment