How to Use sort.Search in Go: Syntax and Examples

In Go, sort.Search is used to find the smallest index in a sorted slice where a condition is true by providing a function that returns a boolean. It performs a binary search and returns the index where the condition first holds, or the length of the slice if none match.

Syntax

The sort.Search function takes two arguments: the length of the slice and a function that takes an index and returns a boolean. It returns the smallest index i in [0, n) for which the function returns true. If no such index exists, it returns n.

Signature:

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

go

index := sort.Search(n, func(i int) bool {
    // return true if condition holds at i
})

Example

This example shows how to use sort.Search to find the index of the first number greater than or equal to 7 in a sorted slice.

go

package main

import (
	"fmt"
	"sort"
)

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

	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, can be inserted at index %d\n", target, index)
	}
}

Output

Found 7 at index 3

Common Pitfalls

• Not ensuring the slice is sorted before using sort.Search can lead to incorrect results.
• Using a condition function that is not monotonic (does not switch from false to true only once) breaks the binary search logic.
• For searching exact matches, always check if the found index actually contains the target value.

go

package main

import (
	"fmt"
	"sort"
)

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

	// Wrong: condition not monotonic (looking for exact match)
	index := sort.Search(len(numbers), func(i int) bool {
		return numbers[i] == target
	})

	fmt.Printf("Wrong search index: %d\n", index)

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

	fmt.Printf("Right search index: %d\n", index)
}

Output

Wrong search index: 6
Right search index: 3

Quick Reference

sort.Search Cheat Sheet:

• n: length of the slice or range to search
• f(i int) bool: function returning true when condition is met at index i
• Returns smallest index i where f(i) is true, or n if none
• Slice must be sorted and f must be monotonic (false then true)

Key Takeaways

Use sort.Search to efficiently find the smallest index where a condition is true in a sorted slice.

The condition function must be monotonic: false values followed by true values only.

Always verify the found index to confirm it matches your target when searching for exact values.

The slice must be sorted for sort.Search to work correctly.

sort.Search returns the length of the slice if no element satisfies the condition.