Двоичный поиск по шагам

Найти первое вхождение числа в отсортированном массиве и проследить сужение полуоткрытого интервала индексов.

Ваш пример

От 1 до 100 чисел в неубывающем порядке. Массив не сортируется автоматически: исходные индексы сохраняют смысл.

Разбор примера

Первый индекс: 1

Состояние до каждого сравнения
LRmida[mid]Следующий шаг
0632R = mid
0312R = mid
0101L = mid+1
  1. Начальный интервал содержит все индексы массива.
  2. Правая граница R не включается; остановка происходит при L=R.
Позиция вставки
1
Размер массива
6

Метод и условия расчёта

Сужаем [L,R), оставляя первое возможное вхождение. При a[mid]<цели переносим L, иначе переносим R. После L=R проверяем равенство.

Вопросы по теме

Почему нужен отсортированный массив?

Без порядка по значению нельзя обоснованно отбросить половину кандидатов. Несортированный ввод отклоняется.

Как считаются индексы?

С нуля. При нескольких равных значениях возвращается самое левое. Если значения нет, отдельно показана позиция вставки с сохранением порядка.

Поиск и сортировка: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.