Binary Search vs Loop Search

binarySearch.go

// /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
}