Презентация «Поиск в отсортированном массиве»
Двоичный поиск проверяет середину отсортированного массива и сужает диапазон. На слайдах этот процесс разобран на семи числах, включая случай, когда искомого значения нет.
О презентации «Поиск в отсортированном массиве»
Порядок элементов нужен, чтобы по одному сравнению решить, какие позиции можно исключить. Если искомое число больше элемента в середине массива, в левой части его быть не может. Если оно меньше среднего элемента, можно исключить правую часть. При равенстве поиск завершается сразу.
Границы задают позиции, которые ещё надо проверить. При нумерации с нуля семь элементов занимают позиции от 0 до 6, начальная середина находится на позиции 3. После каждого сравнения среднюю позицию исключают вместе с ненужной половиной и вычисляют середину заново в новом диапазоне.
При проверке отсутствующего числа диапазон тоже постепенно уменьшается. Алгоритм сообщает, что значение не найдено, когда левая граница становится больше правой. Таблица состояний помогает сверить вычисления. Запишите в каждой строке обе границы, индекс середины и результат сравнения, прежде чем переходить к следующему шагу.
Вопросы по теме «Поиск в отсортированном массиве»
Почему двоичный поиск требует отсортированного массива?
Порядок гарантирует, что слева от середины нет элементов больше среднего, а справа нет элементов меньше него. Без этой гарантии отброшенная часть может содержать искомое значение.
С какой позиции начинается поиск в массиве из семи элементов?
Если элементы пронумерованы от 0 до 6 включительно, первая проверка выполняется на позиции 3. Это четвёртый элемент массива.
Как понять, что число в массиве отсутствует?
Если сравнения сузили диапазон и левая граница стала больше правой, кандидатов больше нет. Этот результат отличается от успешного завершения при равенстве.
Нужна другая тема?
Напишите свою тему или выберите близкую — PREZA подготовит новую презентацию.



























