Golang slices.BinarySearch Function

The slices.BinarySearch 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 of elements. It is particularly useful when you need to efficiently find the index of a target value in a sorted slice, as binary search significantly reduces the time complexity compared to a linear search.

Table of Contents

1. Introduction
2. slices.BinarySearch Function Syntax
3. Examples
   • Basic Usage with Integers
   • Handling Non-Existent Elements
   • Searching in a Slice of Floats
4. Real-World Use Case Example
5. Conclusion

Introduction

The slices.BinarySearch function provides an efficient way to search for an element in a sorted slice. It leverages the binary search algorithm, which has a time complexity of O(log n), making it much faster than a linear search for large datasets. This function is useful in various applications, such as searching in sorted lists, databases, or any scenario where quick lookup times are essential.

slices.BinarySearch Function Syntax

The syntax for the slices.BinarySearch function is as follows:

func BinarySearch[E constraints.Ordered](s []E, target E) (int, bool)

Parameters:

• s []E: The sorted slice in which to search for the target element.
• target E: The target element to search for in the slice.

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 binary search. 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 demonstrates how to use slices.BinarySearch to find an integer in a sorted slice.

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.BinarySearch to search for the target
	index, found := slices.BinarySearch(slice, target)

	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.BinarySearch function searches for the element 30 in the sorted slice [10, 20, 30, 40, 50] and returns the index 2 where it is found.

Handling Non-Existent Elements

This example shows how slices.BinarySearch behaves when the target element is not present in the slice.

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 := 25

	// Use slices.BinarySearch to search for the target
	index, found := slices.BinarySearch(slice, target)

	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 25 not found, should be inserted at index 2

Explanation:

• The slices.BinarySearch function determines that the element 25 is not in the slice and returns the index 2, where 25 should be inserted to maintain the sorted order.

Searching in a Slice of Floats

This example demonstrates how to use slices.BinarySearch to search for a floating-point number in a sorted slice.

Example

package main

import (
	"fmt"
	"slices"
)

func main() {
	// Define a sorted slice of floats
	slice := []float64{1.1, 2.2, 3.3, 4.4, 5.5}
	
	// Define the target value you want to find
	target := 4.4

	// Use slices.BinarySearch to search for the target
	index, found := slices.BinarySearch(slice, target)

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

Output:

Element 4.4 found at index 3

Explanation:

• The slices.BinarySearch function searches for the floating-point number 4.4 in the sorted slice [1.1, 2.2, 3.3, 4.4, 5.5] and returns the index 3 where it is found.

Real-World Use Case Example: Searching for a Product Price

A practical use case for slices.BinarySearch is searching for a product price in a sorted list of prices.

Example: Searching for a Product Price

package main

import (
	"fmt"
	"slices"
)

func main() {
	// Define a sorted slice of product prices
	prices := []float64{19.99, 29.99, 49.99, 99.99, 149.99}
	
	// Define the target price you want to find
	targetPrice := 49.99

	// Use slices.BinarySearch to search for the target price
	index, found := slices.BinarySearch(prices, targetPrice)

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

Explanation:

• The slices.BinarySearch function searches for the product price 49.99 in a sorted list of prices and returns the index where it is found.

Conclusion

The slices.BinarySearch function in Go is used for performing efficient searches in sorted slices. It is particularly useful in scenarios where quick lookups are necessary, such as in large datasets or when searching for specific attributes in a list. By using slices.BinarySearch, you can ensure that your searches are performed with optimal time complexity, making your Go applications more efficient.