Проверка бинарного поиска iOS на облачном Mac

Когда логика работы со списком уже написана в Windows и Swift-код перенесён на облачный Mac для проверки, проще всего упустить не сам поиск элемента, а место вставки повторяющихся значений. Бинарный поиск может использоваться в хронологии чата, шкалах с делениями и индексах упорядоченных записей. Сдвиг на одну позицию не мешает обычным тестам проходить, но на граничных входных данных приводит к потере записей. Ниже мы зададим проверяемый контракт с помощью отдельного скрипта — без запуска симулятора и без зависимости от сетевых данных.

Сначала определим две границы вставки

Пусть на вход поступает массив целых чисел, отсортированный по возрастанию. Нижняя граница возвращает позицию первого элемента, который больше либо равен искомому значению. Верхняя — позицию первого элемента, который строго больше него. Разность верхней и нижней границ равна числу вхождений искомого значения.

Например, для массива [1, 2, 2, 4] и значения 2 нижняя граница равна 1, а верхняя — 3. При поиске 5 обе функции возвращают 4: это позиция вставки в конец, а не признак неудачного поиска.

Возвращаемая позиция может быть равна длине массива, но читать элемент по такому индексу нельзя. Сначала проверьте границы и только затем обращайтесь к элементу. Нельзя подменять позицию вставки в конец индексом последнего элемента.

Здесь мы не используем сигнальное значение -1 и не сортируем массив автоматически внутри функций. Автоматическая сортировка скрыла бы ошибку вызывающего кода, передавшего неупорядоченные данные, а также могла бы нарушить исходный порядок записей относительно друг друга.

Реализуем поиск на полуинтервале

После входа на облачный Mac создайте в своём рабочем каталоге файл BoundsCheck.swift. Сначала выполните xcrun --find swift, чтобы убедиться в доступности набора инструментов, затем добавьте следующую реализацию. Область поиска всегда задаётся полуинтервалом [lo, hi), а начальная правая граница равна длине массива.

func lowerBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

func upperBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] <= target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

Функции отличаются только условием сравнения, но именно оно определяет, по какую сторону границы окажутся повторяющиеся значения. Середина вычисляется как lo + (hi - lo) / 2, без прямого сложения границ. На каждой итерации интервал обязан сужаться. Нельзя присваивать левой границе mid: на массиве из двух элементов это может привести к бесконечному циклу.

Для пустого массива отдельная ветка не нужна: цикл не выполнится ни разу, и функция сразу вернёт ноль. Не вводите count - 1 ради обработки пустого массива — так вы снова получите проблемы с отрицательными индексами и условиями завершения для замкнутого интервала.

Проверим все небольшие массивы по линейному эталону

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

func verify(_ values: [Int]) {
    for target in -1...4 {
        let lower = lowerBound(values, target)
        let upper = upperBound(values, target)
        let expectedLower =
            values.firstIndex(where: { $0 >= target }) ?? values.count
        let expectedUpper =
            values.firstIndex(where: { $0 > target }) ?? values.count

        precondition(lower == expectedLower)
        precondition(upper == expectedUpper)
        precondition(lower <= upper)
        precondition(values[..<lower].allSatisfy { $0 < target })
        precondition(values[lower...].allSatisfy { $0 >= target })
        precondition(values[..<upper].allSatisfy { $0 <= target })
        precondition(values[upper...].allSatisfy { $0 > target })
    }
}

func enumerate(_ prefix: [Int], remaining: Int, minimum: Int) {
    if remaining == 0 {
        verify(prefix)
        return
    }
    for value in minimum...3 {
        enumerate(prefix + [value],
                  remaining: remaining - 1,
                  minimum: value)
    }
}

for length in 0...6 {
    enumerate([], remaining: length, minimum: 0)
}
verify([Int.min, 0, Int.max])
precondition(lowerBound([Int.min, 0, Int.max], Int.min) == 0)
precondition(upperBound([Int.min, 0, Int.max], Int.max) == 3)

Запустите xcrun swift BoundsCheck.swift. Нулевой код завершения означает, что все проверки пройдены; при нарушении условия процесс завершится с ненулевым статусом. В скрипте не используется обычный assert, который может быть удалён в оптимизированной сборке. Не применяйте и параметры компиляции, отключающие проверки безопасности.

Подключим результат к прикладному интерфейсу

Чтобы проверить наличие элемента, сначала найдите нижнюю границу. Совпадение есть только в том случае, если полученная позиция меньше длины массива, а значение по ней равно искомому. Для получения всех повторяющихся значений используйте срез lower..<upper. Если искомого значения нет, срез естественным образом окажется пустым.

Согласуем сортировку и сравнение

Если массив хранит записи, отсортированные по временной метке, поиск должен опираться на ту же семантику временных меток. Если сортировать записи по возрастанию времени, а при поиске сравнивать строки для отображения, корректность самого алгоритма не поможет.

Чтобы сохранить порядок поступления записей с одинаковой временной меткой, можно вставлять их по верхней границе. Если в предметной области есть ещё и приоритеты, сначала определите полный ключ сортировки, а не пытайтесь заменить правила сортировки выбором позиции вставки. Для массива, отсортированного по убыванию, приведённые условия сравнения напрямую не подходят.

Во время поиска массив также должен оставаться неизменным. Если получить позицию асинхронно, а затем изменить массив, прежняя позиция может уже оказаться недействительной. Выполняйте поиск и вставку в одной области изоляции либо работайте с одним и тем же неизменяемым снимком данных.

Превратим неудачные случаи в регрессионные тесты

При включении в тесты проекта сохраните три уровня проверок: фиксированные прикладные сценарии, полный перебор небольших массивов и контракт сортировки реальных записей. Недостаточно проверять лишь то, что результат находится в допустимом диапазоне: допустимая позиция всё равно может быть сдвинута на один элемент.

• Охватите пустой массив, один элемент, массив одинаковых значений и искомые значения за обоими краями диапазона.
• Убедитесь, что все элементы слева от нижней границы меньше искомого значения, а все элементы начиная с верхней границы — строго больше него.
• Проверьте, что длина интервала повторяющихся значений равна числу вхождений, подсчитанному линейным проходом.
• Сохраняйте массив, искомое значение и ожидаемые позиции для каждого сбоя как фиксированный тестовый случай.
• Повторно запускайте проверки с тем набором инструментов и той конфигурацией компиляции, которые используются на практике.

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

Часто задаваемые вопросы