Binary search in Go

gistfile1.go

package main

import "fmt"

func binarySearchRec(elem int, array []int, accesses int) (bool, int) {
	accesses += 1

	if len(array) == 0 {
		return false, accesses
	} else if len(array) == 1 {
		return array[0] == elem, accesses
	}
	middle_idx := (len(array) - 1) /2
	middle := array[middle_idx]

	if middle < elem {
		return binarySearchRec(elem, array[(middle_idx+1):len(array)], accesses)
	} else if middle > elem {
		return binarySearchRec(elem, array[0:middle_idx], accesses)
	}

	return middle == elem, accesses
}

func binarySearch(elem int, array []int) (bool, int) {
	return binarySearchRec(elem, array, 0)

}

func reportTest(result bool, description string) {
	fmt.Println(description)
	if result {
		fmt.Println("PASSED")
	} else {
		fmt.Println("FAIL")
	}
}

func main() {
	var array []int
	var result bool
	var accesses int

	// it should only require Log_2(n) accesses
	array = []int{}
	_, accesses = binarySearch(5, array)
	reportTest(accesses == 1, "length = 0, accesses = 1")

	array = []int{4}
	_, accesses = binarySearch(5, array)
	reportTest(accesses == 1, "length = 1, accesses = 1")

	array = []int{2, 4}
	_, accesses = binarySearch(2, array)
	reportTest(accesses == 1, "length = 2, accesses = 1")

	array = []int{2, 4}
	_, accesses = binarySearch(2, array)
	reportTest(accesses == 1, "length = 2, accesses = 1")

	array = []int{1, 2, 3, 4, 5, 6, 7}
	_, accesses = binarySearch(2, array)
	reportTest(accesses == 2, "length = 7, accesses = 2")

	array = []int{1, 2, 3, 4, 5, 6, 7}
	_, accesses = binarySearch(1, array)
	reportTest(accesses == 3, "length = 7, accesses = 3")

	array = []int{1, 2, 3, 4, 5, 6, 7}
	_, accesses = binarySearch(0, array)
	reportTest(accesses == 3, "length = 7, accesses = 3")
	
	
	array_big := make([]int, 1024) 
	for i, _ := range array_big {
		array_big[i] = i
	}
	
	_, accesses = binarySearch(54, array_big)
	reportTest(accesses == 10, "length = 2^10, accesses = 10")
	
	array_super_big := make([]int, 1048576) 
	for i, _ := range array_super_big {
		array_super_big[i] = i*2
	}
	
	_, accesses = binarySearch(0, array_super_big)
	reportTest(accesses == 20, "length = 2^20, accesses = 20")
	
	result, _ = binarySearch(0, array_super_big)
	reportTest(result == true, "length = 2^20, accesses = 20")
	
	result, _ = binarySearch(1, array_super_big)
	reportTest(result == false, "length = 2^20, accesses = 20")

	array = []int{}
	result, _ = binarySearch(5, array)
	reportTest(result == false, "it should return false when given an empty array")

	array = []int{2}
	result, _ = binarySearch(2, array)
	reportTest(result == true, "it should return true if an item is in the array (length: 1)")

	array = []int{2}
	result, _ = binarySearch(3, array)
	reportTest(result == false, "it should return false if an item is not in the array (length: 1)")

	array = []int{2, 4}
	result, _ = binarySearch(2, array)
	reportTest(result == true, "it should return true if an item is in the array (length: 2)")

	array = []int{2, 4}
	result, _ = binarySearch(4, array)
	reportTest(result == true, "it should return true if an item is in the array (length: 2)")

	array = []int{2, 4}
	result, _ = binarySearch(3, array)
	reportTest(result == false, "it should return false if an item is not in the array (length: 2)")

	array = []int{1, 3, 5, 7, 9}
	result, _ = binarySearch(3, array)
	reportTest(result == true, "it should return true if an item is in the array (length: 5)")

	array = []int{1, 3, 5, 7, 9}
	result, _ = binarySearch(1, array)
	reportTest(result == true, "it should return true if an item is in the array (length: 5)")

	array = []int{1, 3, 5, 7, 9}
	result, _ = binarySearch(2, array)
	reportTest(result == false, "it should return false if an item is not in the array (length: 5)")

	array = []int{1, 3, 5, 7, 11}
	result, _ = binarySearch(3, array)
	reportTest(result == true, "it should return true if an item is not in the array (length: 6)")

	array = []int{1, 3, 5, 7, 11}
	result, _ = binarySearch(5, array)
	reportTest(result == true, "it should return true if an item is not in the array (length: 6)")

	array = []int{1, 3, 5, 7, 11}
	result, _ = binarySearch(7, array)
	reportTest(result == true, "it should return true if an item is not in the array (length: 6)")

	array = []int{1, 3, 5, 7, 11}
	result, _ = binarySearch(6, array)
	reportTest(result == false, "it should return false if an item is not in the array (length: 6)")

	array = []int{1, 3, 5, 7, 11}
	result, _ = binarySearch(4, array)
	reportTest(result == false, "it should return false if an item is not in the array (length: 6)")

	array = []int{1, 3, 5, 7, 11}
	result, _ = binarySearch(0, array)
	reportTest(result == false, "it should return false if an item is not in the array (length: 6)")

	array = []int{1, 3, 5, 7, 11}
	result, _ = binarySearch(12, array)
	reportTest(result == false, "it should return false if an item is not in the array (length: 6)")
}