При a[mid] >= target присвойте right=mid: текущий элемент ещё может быть первым подходящим. При завершении left указывает позицию вставки или первый подходящий элемент.
Как двигать границы в двоичном поиске
При a[mid] >= target присвойте right=mid: текущий элемент ещё может быть первым подходящим. При завершении left указывает позицию вставки или первый подходящий элемент.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Ищем первое значение не меньше target в отсортированном массиве. Интервал [left, right) содержит возможный ответ. Если a[mid] < target, берём left=mid+1. Что делать иначе?
Ответ
При a[mid] >= target присвойте right=mid: текущий элемент ещё может быть первым подходящим. При завершении left указывает позицию вставки или первый подходящий элемент.
Нельзя использовать right=mid−1 в этой полуоткрытой схеме: так можно исключить правильный ответ. Пример [1,3,3,7], target=3 даёт индекс 1. Для пустого массива возвращается 0, для target больше всех — длина массива. Каждая итерация уменьшает интервал, сложность O(log n).