Что делает sort.Search из стандартной библиотеки?

Что делает sort.Search?

Функция sort.Search из стандартной библиотеки Go реализует бинарный поиск. Она принимает два аргумента: целое число n (размер диапазона) и функцию-предикат f func(int) bool. sort.Search находит наименьший индекс i в диапазоне [0, n), для которого f(i) возвращает true. Если такого индекса нет, возвращается n.

Как это работает?

Внутри sort.Search используется классический алгоритм бинарного поиска. Он предполагает, что функция f монотонна: сначала для всех индексов меньше некоторого порога возвращается false, а затем для всех индексов больше или равных порогу — true. Это условие необходимо для корректной работы бинарного поиска.

Пример использования

Допустим, у нас есть отсортированный срез чисел, и мы хотим найти первое число, которое больше или равно 5:

package main

import (
	"fmt"
	"sort"
)

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

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

	if i < len(nums) {
		fmt.Printf("Найден элемент %d на позиции %d\n", nums[i], i)
	} else {
		fmt.Println("Элемент не найден")
	}
}

В этом примере sort.Search вернет индекс 2, так как nums[2] = 5 — первый элемент, удовлетворяющий условию nums[i] >= 5.

Где применяется?

sort.Search полезен в любых сценариях, где нужно найти первую позицию, удовлетворяющую условию, в отсортированной последовательности. Например:

• Поиск элемента в отсортированном массиве.
• Определение места вставки нового элемента для сохранения сортировки.
• Решение задач, связанных с бинарным поиском по ответу (например, поиск минимального значения, при котором выполняется условие).

Вывод

sort.Search — это удобная и эффективная реализация бинарного поиска в Go. Используйте её вместо ручного написания цикла, когда нужно найти первый элемент, удовлетворяющий условию, в отсортированном диапазоне. Это делает код более читаемым и менее подверженным ошибкам.