Двоичный поиск по шагам
Найти первое вхождение числа в отсортированном массиве и проследить сужение полуоткрытого интервала индексов.
Ваш пример
Разбор примера
Первый индекс: 1
| L | R | mid | a[mid] | Следующий шаг |
|---|---|---|---|---|
| 0 | 6 | 3 | 2 | R = mid |
| 0 | 3 | 1 | 2 | R = mid |
| 0 | 1 | 0 | 1 | L = mid+1 |
- Начальный интервал содержит все индексы массива.
- Правая граница R не включается; остановка происходит при L=R.
- Позиция вставки
- 1
- Размер массива
- 6
Метод и условия расчёта
Сужаем [L,R), оставляя первое возможное вхождение. При a[mid]<цели переносим L, иначе переносим R. После L=R проверяем равенство.
Вопросы по теме
Почему нужен отсортированный массив?
Без порядка по значению нельзя обоснованно отбросить половину кандидатов. Несортированный ввод отклоняется.
Как считаются индексы?
С нуля. При нескольких равных значениях возвращается самое левое. Если значения нет, отдельно показана позиция вставки с сохранением порядка.
Поиск и сортировка: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.