benchmark.txt

➤  go test -bench=.
BenchmarkSearch/Div-8         	50000000	        31.5 ns/op
BenchmarkSearch/Shift-8       	100000000	        21.1 ns/op
PASS
ok  	experiments/binarysearch	3.754s

binarysearch.go

package binarysearch

func BinarySearch(s []int, key int) int {
	low := 0
	high := len(s) - 1

	for low <= high {
		middleIndex := (low + high) >> 1
		middleValue := s[middleIndex]

		if middleValue < key {
			low = middleIndex + 1
		} else if middleIndex > key {
			high = middleIndex - 1
		} else {
			return middleIndex
		}
	}
	return -(low + 1)
}

func BinarySearchDiv(s []int, key int) int {
	low := 0
	high := len(s) - 1

	for low <= high {
		middleIndex := (low + high) / 2
		middleValue := s[middleIndex]

		if middleValue < key {
			low = middleIndex + 1
		} else if middleIndex > key {
			high = middleIndex - 1
		} else {
			return middleIndex
		}
	}
	return -(low + 1)
}

binarysearch_test.go

package binarysearch

import "testing"

const Max = 1000000

func generateSlice() []int {
	s := make([]int, Max)
	for x := 0; x < Max; x++ {
		s[x] = x
	}
	return s
}

func BenchmarkSearch(b *testing.B) {
	s := generateSlice()
	b.Run("Div", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			BinarySearchDiv(s, Max)
		}
	})

	b.Run("Shift", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			BinarySearch(s, Max)
		}
	})
}