karate.go

package karate

func Chop(n int, items []int) int {
	if len(items) == 0 {
		return -1
	}

	var key = len(items) / 2
	var keyFound int
	switch {
	case n == items[key]:
		keyFound = key
	case n >= items[key]:
		keyFound = Chop(n, items[key:])
	case n <= items[key]:
		keyFound = Chop(n, items[:key])
	}

	return keyFound
}

karate_test.go

package karate_test

import (
	"github.com/wingyplus/kata/karate"
	"testing"
)

func AssertEquals(t *testing.T, actual int, expect int) {
	if actual != expect {
		t.Errorf("expect %d but was %d\n", expect, actual)
	}
}

func TestKarateChopShouldBeReturnMinusOneWhenNotFound(t *testing.T) {
	AssertEquals(t, karate.Chop(3, []int{}), -1)
}

func TestKarateChopShouldBeReturnIndexWhenGivenNumberInList(t *testing.T) {
	AssertEquals(t, karate.Chop(3, []int{3}), 0)
	AssertEquals(t, karate.Chop(3, []int{1, 3}), 1)

	AssertEquals(t, karate.Chop(5, []int{1, 3, 5, 7}), 2)
}

var List100Items = List(100)
var List1_000_000Items = List(1000)

func List(n int) []int {
	var items []int
	for i := 0; i < n; i++ {
		items = append(items, n)
	}
	return items
}

func BenchmarkKarateChopAt100Items(b *testing.B) {
	for i := 0; i < b.N; i++ {
		karate.Chop(90, List100Items)
	}
}

func BenchmarkKarateChopAt1_000_000Items(b *testing.B) {
	for i := 0; i < b.N; i++ {
		karate.Chop(600000, List1_000_000Items)
	}
}

test_benchmark

$ go test -bench . -v ./...
?   	github.com/wingyplus/kata	[no test files]
=== RUN TestKarateChopShouldBeReturnMinusOneWhenNotFound
--- PASS: TestKarateChopShouldBeReturnMinusOneWhenNotFound (0.00 seconds)
=== RUN TestKarateChopShouldBeReturnIndexWhenGivenNumberInList
--- PASS: TestKarateChopShouldBeReturnIndexWhenGivenNumberInList (0.00 seconds)
PASS
BenchmarkKarateChopAt100Items	10000000	       189 ns/op
BenchmarkKarateChopAt1_000_000Items	    1000	   2228706 ns/op
ok  	github.com/wingyplus/kata/karate	4.703s


# With Binary Search
$ go test -bench . -v ./...
?   	github.com/wingyplus/kata	[no test files]
=== RUN TestKarateChopShouldBeReturnMinusOneWhenNotFound
--- PASS: TestKarateChopShouldBeReturnMinusOneWhenNotFound (0.00 seconds)
=== RUN TestKarateChopShouldBeReturnIndexWhenGivenNumberInList
--- PASS: TestKarateChopShouldBeReturnIndexWhenGivenNumberInList (0.00 seconds)
PASS
BenchmarkKarateChopAt100Items	20000000	        76.6 ns/op
BenchmarkKarateChopAt1_000_000Items	10000000	       226 ns/op
ok  	github.com/wingyplus/kata/karate	4.296s