Как реализовать бинарный поиск в отсортированном массиве с уникальными элементами?

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

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

Как отвечать

Начните с инварианта. Удобнее всего полуоткрытый интервал [lo, hi): искомое, если оно есть, лежит внутри, пустой интервал означает «не найдено».

• границы: size_t lo = 0, hi = a.size(); и цикл while (lo < hi). Пустой вектор обрабатывается сам, без особого случая;
• середина: mid = lo + (hi - lo) / 2. Запись (lo + hi) / 2 переполняется на знаковых int при больших индексах, эта ошибка годами жила даже в стандартной библиотеке Java. В C++20 для этого есть std::midpoint;
• шаг: если a[mid] < target, то lo = mid + 1, иначе hi = mid. После цикла lo указывает на первый элемент не меньше target, остаётся проверить lo < a.size() && a[lo] == target;
• сложность: O(log n) сравнений и O(1) памяти, для миллиона элементов это около 20 шагов.

Потом покажите знание стандартной библиотеки: std::lower_bound и std::ranges::lower_bound возвращают итератор на первый элемент не меньше искомого, std::binary_search отвечает только «есть или нет», std::equal_range отдаёт диапазон равных. Уникальность в условии значит, что найденный индекс однозначен. С дубликатами вариант с ранним return mid вернёт произвольное вхождение, и тогда нужен именно lower_bound.

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

Смешивают два стиля границ: закрытый интервал [lo, hi] с условием while (lo < hi). Когда остаётся один кандидат, цикл выходит, не проверив его, и поиск промахивается по крайнему элементу.

Пишут lo = mid вместо lo = mid + 1. Когда остаются два элемента, середина округляется вниз, левая граница перестаёт сдвигаться, и цикл становится бесконечным.

Берут беззнаковые индексы в закрытом варианте. hi = a.size() - 1 на пустом векторе и hi = mid - 1 при mid == 0 превращаются в огромное size_t, условие lo <= hi остаётся истинным, и следующая итерация читает за пределами массива.