Функция sort.Search

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

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

Синтаксис

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

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

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

gopackage 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)
}

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

go3

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

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

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

gopackage 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)
  }
}

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

go"found at index 3"

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

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

gopackage 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])
}

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

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

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

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

gopackage 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)
}

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

go0

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

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