Generic Binary Search in Go

Read more articles on Go, Algorithms
Generic Binary Search in Go

Subscribe

Get updated 1 - 2 times a month when new articles are published, no spam ever.

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'

Subscribe

Get updated 1 - 2 times a month when new articles are published, no spam ever.

    TheDeveloperCafe Ā© 2022-2024