Как работает бинарный поиск

Что проверяют

Понимаете ли вы алгоритм и его условие применимости. Вопрос базовый, поэтому ценится точность формулировок, а не пересказ.

Как отвечать

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

Функция НайтиИндекс(Массив, Искомое)
    Лево = 0;
    Право = Массив.Количество() - 1;
    Пока Лево <= Право Цикл
        Середина = Лево + Цел((Право - Лево) / 2);
        Если Массив[Середина] = Искомое Тогда
            Возврат Середина;
        ИначеЕсли Массив[Середина] < Искомое Тогда
            Лево = Середина + 1;
        Иначе
            Право = Середина - 1;
        КонецЕсли;
    КонецЦикла;
    Возврат -1;
КонецФункции

Сложность O(log n) по времени и O(1) по памяти в итеративном варианте. Миллион элементов это двадцать сравнений вместо миллиона.

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

Где спотыкаются

Пишут Середина = (Лево + Право) / 2 и в языках с фиксированной разрядностью получают переполнение. Безопасная форма это Лево + (Право - Лево) / 2.

Путают границы и получают вечный цикл или потерянный элемент: важно, что при уходе вправо берётся Середина + 1, а не Середина.

Забывают сказать про обязательную сортировку.

Не могут ответить, что вернуть, если элемента нет, хотя на практике чаще нужна позиция вставки, а не просто минус один.