Какова алгоритмическая сложность бинарного поиска и каковы условия его применения?

Бинарный поиск имеет логарифмическую временную сложность O(log n).

Основное условие применения: алгоритм работает только на отсортированных данных (массивах, срезах).

Принцип работы:
На каждом шаге алгоритм сравнивает искомый элемент со средним элементом коллекции. Если они не равны, то в зависимости от результата сравнения отбрасывается либо левая, либо правая половина коллекции. Таким образом, область поиска сокращается вдвое на каждой итерации.

Применение в Go:
Вместо написания своей реализации, рекомендуется использовать готовые функции из пакета sort, которые эффективны и протестированы:

import (
    "fmt"
    "sort"
)

func main() {
    slice := []int{2, 5, 8, 12, 16, 23, 38, 56, 72}
    target := 23

    // sort.SearchInts возвращает индекс, куда можно вставить target
    // с сохранением сортировки. Если элемент найден, это его индекс.
    index := sort.SearchInts(slice, target)

    if index < len(slice) && slice[index] == target {
        fmt.Printf("Элемент %d найден по индексу %dn", target, index)
    } else {
        fmt.Printf("Элемент %d не найденn", target)
    }
}