Golang slices.BinarySearchFunc Function

The slices.BinarySearchFunc function in Golang is part of the slices package, introduced in Go 1.21 as part of the standard library. This function allows you to perform a binary search on a sorted slice using a custom comparison function, making it particularly useful when you need to search within complex types or when default comparison operators are insufficient.

Table of Contents

1. Introduction
2. slices.BinarySearchFunc Function Syntax
3. Examples
   • Basic Usage with Integers
   • Searching in a Slice of Structs
   • Searching with Custom Comparison Logic
4. Real-World Use Case Example
5. Conclusion

Introduction

The slices.BinarySearchFunc function provides a flexible way to perform binary searches on sorted slices in Go. Unlike slices.BinarySearch, which works with simple types and uses default comparison operators, slices.BinarySearchFunc allows you to define your own comparison logic, making it ideal for searching within slices of complex types or for implementing custom ordering.

slices.BinarySearchFunc Function Syntax

The correct syntax for the slices.BinarySearchFunc function is as follows:

func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool)

Parameters:

• x S: The sorted slice in which to search for the target element.
• target T: The target element to search for in the slice.
• cmp func(E, T) int: The comparison function that compares an element from the slice (E) with the target (T). It should return:
  • A negative number if the slice element is less than the target.
  • Zero if they are equal.
  • A positive number if the slice element is greater than the target.

Returns:

• int: The index of the target element in the slice if found, or the index where the element would be inserted if not found.
• bool: A boolean value indicating whether the target element was found in the slice.

Behavior:

• Performs a binary search: The function searches for the target element in the sorted slice using the provided comparison function. If the target is found, it returns the index and true. If not found, it returns the insertion index and false.

Examples

Basic Usage with Integers

This example shows how to use slices.BinarySearchFunc to find an integer in a sorted slice using a custom comparison function.

Example

package main

import (
	"fmt"
	"slices"
)

func main() {
	// Define a sorted slice of integers
	slice := []int{10, 20, 30, 40, 50}
	
	// Define the target value you want to find
	target := 30

	// Use slices.BinarySearchFunc to search for the target
	index, found := slices.BinarySearchFunc(slice, target, func(a int, b int) int {
		return a - b
	})

	if found {
		fmt.Printf("Element %d found at index %d\n", target, index)
	} else {
		fmt.Printf("Element %d not found, should be inserted at index %d\n", target, index)
	}
}

Output:

Element 30 found at index 2

Explanation:

• The slices.BinarySearchFunc function searches for the element 30 in the sorted slice [10, 20, 30, 40, 50] using a custom comparison function and returns the index 2 where it is found.

Searching in a Slice of Structs

This example demonstrates how to use slices.BinarySearchFunc to search for an element in a slice of structs, where the search is based on a specific field.

Example

package main

import (
	"fmt"
	"slices"
)

type Person struct {
	Name string
	Age  int
}

func main() {
	// Define a sorted slice of structs
	people := []Person{
		{"Bob", 25},
		{"Alice", 30},
		{"Charlie", 35},
	}

	// Define the target age you want to search for
	targetAge := 30

	// Use slices.BinarySearchFunc to search for the person with the target age
	index, found := slices.BinarySearchFunc(people, targetAge, func(p Person, age int) int {
		return p.Age - age
	})

	if found {
		fmt.Printf("Person with age %d found at index %d: %+v\n", targetAge, index, people[index])
	} else {
		fmt.Printf("Person with age %d not found, should be inserted at index %d\n", targetAge, index)
	}
}

Output:

Person with age 30 found at index 1: {Name:Alice Age:30}

Explanation:

• The slices.BinarySearchFunc function searches for a Person struct with age 30 in a sorted slice of Person structs. The comparison function is based on the Age field.

Searching with Custom Comparison Logic

This example demonstrates how to use slices.BinarySearchFunc to search for an element using custom comparison logic, such as searching by a specific field or attribute.

Example

package main

import (
	"fmt"
	"slices"
)

type Product struct {
	Name  string
	Price float64
}

func main() {
	// Define a sorted slice of products
	products := []Product{
		{"Tablet", 500.25},
		{"Smartphone", 800.00},
		{"Laptop", 1200.50},
	}

	// Define the target price you want to search for
	targetPrice := 800.00

	// Use slices.BinarySearchFunc to search for the product with the target price
	index, found := slices.BinarySearchFunc(products, targetPrice, func(p Product, price float64) int {
		if p.Price < price {
			return -1
		} else if p.Price > price {
			return 1
		}
		return 0
	})

	if found {
		fmt.Printf("Product with price %.2f found at index %d: %+v\n", targetPrice, index, products[index])
	} else {
		fmt.Printf("Product with price %.2f not found, should be inserted at index %d\n", targetPrice, index)
	}
}

Output:

Product with price 800.00 found at index 1: {Name:Smartphone Price:800}

Explanation:

• The slices.BinarySearchFunc function searches for a product with price 800.00 in a sorted slice of products. The comparison function compares the Price field.

Real-World Use Case Example: Searching for a Student by Grade

A practical use case for slices.BinarySearchFunc is searching for a student in a sorted list by their grade.

Example: Searching for a Student by Grade

package main

import (
	"fmt"
	"slices"
)

type Student struct {
	Name  string
	Grade float64
}

func main() {
	// Define a sorted slice of students
	students := []Student{
		{"Charlie", 85.0},
		{"Alice", 88.5},
		{"Bob", 92.3},
	}

	// Define the target grade you want to search for
	targetGrade := 88.5

	// Use slices.BinarySearchFunc to search for the student with the target grade
	index, found := slices.BinarySearchFunc(students, targetGrade, func(s Student, grade float64) int {
		if s.Grade < grade {
			return -1
		} else if s.Grade > grade {
			return 1
		}
		return 0
	})

	if found {
		fmt.Printf("Student with grade %.2f found at index %d: %+v\n", targetGrade, index, students[index])
	} else {
		fmt.Printf("Student with grade %.2f not found, should be inserted at index %d\n", targetGrade, index)
	}
}

Output:

Student with grade 88.50 found at index 1: {Name:Alice Grade:88.5}

Explanation:

• The slices.BinarySearchFunc function searches for a student with grade 88.5 in a sorted list of students. The comparison function compares the Grade field.

Conclusion

The slices.BinarySearchFunc function in Go is used for performing binary searches on slices with custom comparison logic. It is particularly useful when searching in slices of complex types or when you need to implement custom ordering criteria. By using slices.BinarySearchFunc, you can efficiently perform searches tailored to the specific needs of your Go applications.