Golang sort.Search Function

The sort.Search function in Golang is part of the sort package and is used to perform a binary search on a sorted slice or array. It efficiently finds the smallest index at which a given condition is true. This function is highly useful when working with large sorted datasets, where linear search would be inefficient.

Table of Contents

1. Introduction
2. sort.Search Function Syntax
3. Examples
   • Basic Usage
   • Searching for a Specific Value
   • Custom Search Conditions
4. Real-World Use Case Example
5. Conclusion

Introduction

The sort.Search function is used for searching through sorted data in Golang. It uses a binary search algorithm, which is much faster than a linear search, especially for large datasets. This function doesn’t search for a specific value directly but instead relies on a user-defined condition (predicate function) to determine the search criteria.

sort.Search Function Syntax

The syntax for the sort.Search function is as follows:

func Search(n int, f func(int) bool) int

Parameters:

• n: The number of elements in the slice or array to search.
• f: A predicate function that takes an index int as input and returns a boolean value. The function should return true when the desired condition is met.

Returns:

• int: The smallest index at which the predicate function returns true. If no such index exists, it returns n.

Examples

Basic Usage

This example demonstrates how to use sort.Search to find the first index where a condition is true in a sorted slice of integers.

Example

package main

import (
	"fmt"
	"sort"
)

func main() {
	numbers := []int{1, 3, 5, 7, 9, 11, 13, 15, 17}

	index := sort.Search(len(numbers), func(i int) bool {
		return numbers[i] >= 10
	})

	if index < len(numbers) {
		fmt.Printf("First number greater than or equal to 10 found at index %d: %d\n", index, numbers[index])
	} else {
		fmt.Println("No number greater than or equal to 10 found.")
	}
}

Output:

First number greater than or equal to 10 found at index 5: 11

Explanation:

• The sort.Search function searches the sorted numbers slice and returns the index of the first element that is greater than or equal to 10.
• The index and the corresponding value are printed.

Searching for a Specific Value

This example shows how to use sort.Search to find the index of a specific value in a sorted slice.

Example

package main

import (
	"fmt"
	"sort"
)

func main() {
	numbers := []int{1, 3, 5, 7, 9, 11, 13, 15, 17}
	target := 13

	index := sort.Search(len(numbers), func(i int) bool {
		return numbers[i] >= target
	})

	if index < len(numbers) && numbers[index] == target {
		fmt.Printf("Found %d at index %d\n", target, index)
	} else {
		fmt.Printf("%d not found in the slice.\n", target)
	}
}

Output:

Found 13 at index 6

Explanation:

• The sort.Search function looks for the target value (13) in the sorted numbers slice.
• If the value is found at the returned index, it prints the index and value. If not, it indicates that the target is not found.

Custom Search Conditions

This example demonstrates how to use sort.Search with a custom condition on a slice of structs.

Example

package main

import (
	"fmt"
	"sort"
)

type Product struct {
	Name  string
	Price float64
}

func main() {
	products := []Product{
		{"Product A", 19.99},
		{"Product B", 29.99},
		{"Product C", 49.99},
		{"Product D", 59.99},
	}

	maxPrice := 50.00
	index := sort.Search(len(products), func(i int) bool {
		return products[i].Price > maxPrice
	})

	if index < len(products) {
		fmt.Printf("First product with a price greater than $%.2f: %s, $%.2f\n", maxPrice, products[index].Name, products[index].Price)
	} else {
		fmt.Printf("No product found with a price greater than $%.2f\n", maxPrice)
	}
}

Output:

First product with a price greater than $50.00: Product D, $59.99

Explanation:

• The sort.Search function is used to find the first product in the products slice with a price greater than $50.00.
• The index of the first matching product is returned, and the product details are printed.

Real-World Use Case Example: Finding the First Available Room in a Hotel

Suppose you have a list of rooms sorted by availability times, and you want to find the first available room that is free after a certain time.

Example: Finding the First Available Room

package main

import (
	"fmt"
	"sort"
	"time"
)

type Room struct {
	Number   int
	FreeFrom time.Time
}

func main() {
	now := time.Now()
	rooms := []Room{
		{101, now.Add(2 * time.Hour)},
		{102, now.Add(4 * time.Hour)},
		{103, now.Add(1 * time.Hour)},
		{104, now.Add(3 * time.Hour)},
	}

	sort.Slice(rooms, func(i, j int) bool {
		return rooms[i].FreeFrom.Before(rooms[j].FreeFrom)
	})

	desiredTime := now.Add(2 * time.Hour)
	index := sort.Search(len(rooms), func(i int) bool {
		return rooms[i].FreeFrom.After(desiredTime)
	})

	if index < len(rooms) {
		fmt.Printf("First available room after %v: Room %d, free from %v\n", desiredTime, rooms[index].Number, rooms[index].FreeFrom)
	} else {
		fmt.Println("No rooms available after the desired time.")
	}
}

Output:

First available room after 2024-08-11 14:00:00 +0000 UTC: Room 102, free from 2024-08-11 16:00:00 +0000 UTC

Explanation:

• The rooms slice is sorted by the FreeFrom time, and sort.Search is used to find the first room that is available after a specific time.
• The details of the first matching room are printed.

Conclusion

The sort.Search function in Go is used for efficiently finding elements in sorted slices or arrays. It allows for flexible search conditions, making it applicable to a wide range of scenarios. Whether you’re searching for specific values, filtering data, or working with custom data structures, sort.Search provides a fast and reliable way to locate the elements you need.