binary_search.go

package binary_search

import "errors"

// For testing:
// var Find = FindRecursive
var Find = FindIterative

func FindRecursive(list []int, num int) (int, error) {
	if len(list) == 0 {
		return -1, errors.New("Not found")
	}

	midIdx := len(list) / 2

	if list[midIdx] == num {
		return midIdx, nil
	}

	if list[midIdx] > num {
		return FindRecursive(list[:midIdx], num)
	}

	newStart := midIdx + 1
	idx, err := FindRecursive(list[newStart:], num)

	if err != nil {
		return -1, err
	}

	return idx + newStart, nil
}

func FindIterative(list []int, num int) (int, error) {
	beg := 0
	end := len(list) - 1

	for beg <= end {
		mid := (beg + end) / 2
		switch {
		case list[mid] == num:
			return mid, nil
		case list[mid] < num:
			beg = mid + 1
		case list[mid] > num:
			end = mid - 1
		}
	}

	return -1, errors.New("Not found")
}

binary_search_test.go

package binary_search

import "testing"

func TestEmptyList(t *testing.T) {
	_, err := Find([]int{}, 42)

	if err == nil {
		t.Error("should return error when called on empty list")
	}
}

func TestFindMiddleElement(t *testing.T) {
	idx, err := Find([]int{1, 2, 3, 4, 5}, 3)

	if err != nil {
		t.Error(err)
	}

	if idx != 2 {
		t.Errorf("wrong position: %d instead of %d", idx, 3)
	}
}

func TestSearcHeadElement(t *testing.T) {
	idx, err := Find([]int{1, 2, 3, 4, 5, 6, 7, 8}, 1)

	if err != nil {
		t.Error(err)
	}

	if idx != 0 {
		t.Errorf("wrong position: %d instead of %d", idx, 0)
	}
}

func TestFindLastElement(t *testing.T) {
	idx, err := Find([]int{1, 2, 3, 4, 5, 6, 7, 8}, 8)

	if err != nil {
		t.Error(err)
	}

	if idx != 7 {
		t.Errorf("wrong position: %d instead of %d", idx, 7)
	}
}

func TestFindFailToBig(t *testing.T) {
	idx, err := Find([]int{1, 2, 3, 4, 5, 6}, 88)

	if err == nil {
		t.Error("must return error when element is not fould")
	}

	if idx != -1 {
		t.Errorf("%d != %d", idx, -1)
	}
}

func TestFindFailToSmall(t *testing.T) {
	idx, err := Find([]int{1, 2, 3, 4, 5, 6}, -3)

	if err == nil {
		t.Error("must return error when element is not fould")
	}

	if idx != -1 {
		t.Errorf("%d != %d", idx, -1)
	}
}