Последовательности и двоичный поиск по границе

Каталог хранит отсортированные номера [2, 4, 4, 9]. Нужно вставить новое число 4 перед первым существующим 4. Линейный поиск подходит, но отсортированность позволяет отбрасывать сразу половину оставшегося диапазона.

Массив, срез и связный список

Массив хранит фиксированное число элементов; срез Go задаёт доступ к части массива, длину и ёмкость. Индексный доступ O(1) не означает бесплатную вставку в середину: хвост нужно сдвинуть. Два среза могут ссылаться на одно хранилище, поэтому изменение одного меняет видимые элементы другого. Для независимой копии выделите новый срез и используйте copy или append в новое хранилище.

В связном списке узел хранит значение и ссылку на следующий узел. Вставка после уже известного узла занимает O(1), но найти узел по номеру позиции обычно стоит O(n). Список использует дополнительную память на ссылки и часто хуже использует локальность кеша процессора. Выбор структуры начинается с нужных операций, а не со списка преимуществ без условий.

Двоичный поиск требует дешёвого доступа к середине. Отсортированный связный список не превращает поиск автоматически в O(log n): продвижение до очередной середины тоже имеет цену.

Ищем первую подходящую позицию

Договор LowerBound: вернуть наименьший индекс i, для которого a[i] >= target. Если такой позиции нет, вернуть len(a). На пустом входе ответ 0. Вход отсортирован по возрастанию и не изменяется.

func LowerBound(a []int, target int) int {
    lo, hi := 0, len(a)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if a[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

Рабочий диапазон полуоткрытый: [lo, hi). Всё левее lo строго меньше цели, всё начиная с hi не меньше цели. Значение hi=len(a) допустимо как граница, но читать a[hi] нельзя. При завершении lo=hi, а две известные области соприкасаются в нужной точке.

Для цели 4 на [2,4,4,9]: lo=0,hi=4,mid=2; значение 4 подходит, значит hi=2. Затем mid=1 и hi=1. Затем mid=0, значение 2 меньше цели, lo=1. Ответ 1. В варианте lo=mid последняя итерация могла бы никогда не изменить границу.

От границы к поиску значения

После получения i сравните i < len(a) && a[i] == target. Проверка границы должна стоять первой: короткое замыкание не позволяет читать a[len(a)]. Нижняя граница не означает, что число существует. Для цели 5 она равна 3, а значение на позиции 3 — 9.

За шаг диапазон уменьшается примерно вдвое; итераций O(log n), памяти O(1). Но вставка по найденной позиции по-прежнему требует сдвига O(n). Быстрый поиск позиции не делает всю операцию логарифмической.

Самостоятельная лаборатория

В заготовке exercises реализуйте LowerBound и запустите go test ./exercises -run TestLowerBound. Допишите тесты для цели меньше всех, больше всех, отрицательных значений и списка из одинаковых чисел. Для всех целей от −3 до 12 сравните результат с простым линейным эталоном на нескольких небольших отсортированных массивах.

Затем реализуйте UpperBound: первую позицию, где значение строго больше цели. Число копий target равно upper−lower. Сформулируйте новый инвариант, а не меняйте знак сравнения по памяти. Практика — 40 минут.

Критерии готовности: пустой вход корректен; повторения возвращают первую границу; каждая итерация уменьшает диапазон; вход сохраняется; проверяется предусловие сортировки в тестовых данных. Сортировать внутри LowerBound нельзя: это меняет договор и стоимость.

Разбор

Верхняя граница меняет ветвление: a[mid] <= target продвигает lo. Для [4,4,4] lower=0,upper=3. Любая найденная копия дала бы неверный подсчёт количества. В стандартной библиотеке sort.Search обобщает поиск границы монотонного условия. Проверять условие на неотсортированном массиве нельзя без отдельного доказательства монотонности.

Источники: Go: slices, Princeton: поиск, sort.Search.