Есть ли в стандартной библиотеке Go функция бинарного поиска?

Функция бинарного поиска в Go

В стандартной библиотеке Go действительно есть функция бинарного поиска. Она находится в пакете sort и называется sort.Search. Эта функция позволяет эффективно находить индекс элемента в отсортированном срезе, используя алгоритм бинарного поиска.

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

Функция sort.Search принимает два аргумента: длину среза и функцию-предикат. Она находит наименьший индекс i, для которого предикат возвращает true. Если такого индекса нет, возвращается длина среза.

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Отсортированный срез целых чисел
	numbers := []int{1, 3, 5, 7, 9, 11, 13}

	// Ищем число 7
	target := 7
	index := sort.Search(len(numbers), func(i int) bool {
		return numbers[i] >= target
	})

	if index < len(numbers) && numbers[index] == target {
		fmt.Printf("Найдено число %d на позиции %d\n", target, index)
	} else {
		fmt.Printf("Число %d не найдено\n", target)
	}
}

Применение

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

Вывод

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