Функция sort.Search

Функция sort.Search из пакета sort реализует бинарный поиск в отсортированном слайсе. Она принимает два аргумента: количество элементов n (длину слайса) и функцию f, которая определяет условие поиска. Функция возвращает индекс i, начиная с которого условие f(i) становится истинным. Если подходящий индекс не найден, возвращается n.

Важное условие: слайс должен быть отсортирован по возрастанию, а функция f должна быть монотонной (то есть возвращать false для всех индексов меньше искомого и true для всех индексов больше или равных искомому).

Синтаксис

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

Поиск в слайсе целых чисел

Найдем позицию для вставки числа 4 в отсортированном слайсе целых чисел:

package main

import (
	"fmt"
	"sort"
)

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

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

	fmt.Println(pos)
}

Результат выполнения кода:

3

Функция вернула индекс 3, так как элемент 4 должен стоять между индексами 2 (значение 3) и 3 (значение 5).

Поиск элемента в слайсе строк

Выполним поиск строки "d" в отсортированном слайсе строк:

package main

import (
	"fmt"
	"sort"
)

func main() {
	letters := []string{"a", "b", "c", "d", "e"}
	target := "d"

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

	if pos < len(letters) && letters[pos] == target {
		fmt.Println("found at index", pos)
	} else {
		fmt.Println("not found, would insert at index", pos)
	}
}

Результат выполнения кода:

"found at index 3"

Поиск по сложному условию

Найдем индекс первого числа, которое больше 3 в отсортированном слайсе:

package main

import (
	"fmt"
	"sort"
)

func main() {
	numbers := []int{1, 2, 3, 4, 5, 6}

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

	fmt.Println("First number > 3 is at index", pos)
	fmt.Println("Value:", numbers[pos])
}

Результат выполнения кода:

"First number > 3 is at index 3"
"Value: 4"

Поиск в пустом слайсе

Проверим поведение функции на пустом слайсе:

package main

import (
	"fmt"
	"sort"
)

func main() {
	var empty []int

	pos := sort.Search(len(empty), func(i int) bool {
		return empty[i] >= 5
	})

	fmt.Println(pos)
}

Результат выполнения кода:

0

Для пустого слайса функция всегда возвращает 0, так как функция-предикат ни разу не вызывается.

Смотрите также

функцию sort.SearchInts,
которая выполняет бинарный поиск в слайсе целых чисел
функцию sort.SearchStrings,
которая выполняет бинарный поиск в слайсе строк
функцию sort.SearchFloat64s,
которая выполняет бинарный поиск в слайсе чисел с плавающей точкой
функцию slices.BinarySearch,
которая выполняет бинарный поиск в слайсе любого типа