binary_vs_linear_search.go

package main

import (
	"testing"
)

/*
go test -v .
=== RUN   TestBinarySearch
--- PASS: TestBinarySearch (0.00s)
PASS
ok  	github.com/ggirtsou/benchmark	0.001s

go test -bench=.
goos: linux
goarch: amd64
pkg: github.com/ggirtsou/benchmark
BenchmarkBinarySearch-8   	20000000	        52.2 ns/op
BenchmarkLinearSearch-8   	  300000	      4030 ns/op
PASS
*/

func BenchmarkBinarySearch(b *testing.B) {
	data := getData()
	for n := 0; n < b.N; n++ {
		binarySearch(data, 12345, 0)
	}
}

func BenchmarkLinearSearch(b *testing.B) {
	data := getData()
	for n := 0; n < b.N; n++ {
		linearSearch(data, 12345, 0)
	}
}

func TestBinarySearch(t *testing.T) {
	var testCases = []struct {
		elements            []int
		target              int
		binaryExpectedSteps int
	}{
		{
			elements:            []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
			target:              2,
			binaryExpectedSteps: 2,
		},
		{
			elements:            []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
			target:              4,
			binaryExpectedSteps: 4,
		},
		{
			// has to be sorted
			elements:            []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 90, 100, 1000},
			target:              90,
			binaryExpectedSteps: 3,
		},
	}

	for _, testCase := range testCases {
		steps := binarySearch(testCase.elements, testCase.target, 0)
		if testCase.binaryExpectedSteps != steps {
			t.Errorf(
				"binary search was supposed to be done in %d steps, instead %d steps were made",
				testCase.binaryExpectedSteps,
				steps,
			)
		}

		linearIdx, _ := linearSearch(testCase.elements, testCase.target, 0)
		if testCase.elements[linearIdx] != testCase.target {
			t.Errorf("linear search was supposed to find %d but found %d", testCase.target, testCase.elements[linearIdx])
		}
	}
}

func linearSearch(elems []int, target, steps int) (int, int) {
	for i, v := range elems {
		steps++
		if v == target {
			return i, steps
		}
	}

	panic("not found")
}

// assumes sorted slice was provided. returns total steps took to find answer
func binarySearch(elems []int, target, steps int) int {
	steps++
	idx := len(elems) / 2
	split := elems[idx-1]

	if len(elems) == 0 || len(elems) == 1 && elems[0] != target {
		panic("not found")
	}

	if split == target {
		return steps
	}

	if split < target {
		return binarySearch(elems[idx:], target, steps)
	}

	return binarySearch(elems[:idx], target, steps)
}

func getData() (data []int) {
	for i := 0; i < 1000000; i++ {
		data = append(data, i)
	}

	return
}