Generic Binary Search in Go

Generic Binary Search Function #

Below is an implement of a generic binary search in Go that works on a slice of any type.

It returns the index of target element and a boolean denoting if the element is found.

 
go
 func binarySearch[T any](l []T, item T, compare func(i, j T) int) (int, bool) {
	start := 0
	end := len(l) - 1

	for start <= end {
		mid := start + ((end - start) / 2)

		c := compare(item, l[mid])

		if c == 0 {
			return mid, true
		}

		if c < 0 {
			end = mid - 1
		} else {
			start = mid + 1
		}
	}

	return -1, false
}

The function takes in a compare function as an argument which should denote if the element i is less/greater than or equal to the element j.

• 0 means i is equal to j
• -1 means i is less than j
• 1 means i is greater that j

Example Usage #

 
go
 package main

import (
	"fmt"
	"strings"
)

func main() {
	index, has := binarySearch(
	    []int{1, 2, 3, 4, 5, 6, 7, 8, 9}, 
	    4, 
	    func(i, j int) int { return i - j },
	)
	if has {
		fmt.Println("number 4 found at index", index)
	} else {
		fmt.Println("list doesn't have number 4")
	}

	index, has = binarySearch(
	    []string{"a", "b", "c", "d", "e"}, 
	    "d",
	    func(i, j string) int { return strings.Compare(i, j) },
    )
	if has {
		fmt.Println("'d' found at index", index)
	} else {
		fmt.Println("list doesn't have 'd'")
	}

	index, has = binarySearch(
	    []string{"a", "b", "c", "d", "e"}, 
	    "f", 
	    func(i, j string) int { return strings.Compare(i, j) },
    )
	if has {
		fmt.Println("'f' found at index", index)
	} else {
		fmt.Println("list doesn't have 'f'")
	}
}
main.go

Output

number 4 found at index 3
'd' found at index 3
list doesn't have 'f'