Перейти к презентации

Презентация «Поиск в отсортированном массиве»

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

Слайд 1 / 10
  1. Слайд 1 «Двоичный поиск» из презентации «Поиск в отсортированном массиве».

О презентации «Поиск в отсортированном массиве»

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

Границы задают позиции, которые ещё надо проверить. При нумерации с нуля семь элементов занимают позиции от 0 до 6, начальная середина находится на позиции 3. После каждого сравнения среднюю позицию исключают вместе с ненужной половиной и вычисляют середину заново в новом диапазоне.

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

Вопросы по теме «Поиск в отсортированном массиве»

Почему двоичный поиск требует отсортированного массива?

Порядок гарантирует, что слева от середины нет элементов больше среднего, а справа нет элементов меньше него. Без этой гарантии отброшенная часть может содержать искомое значение.

С какой позиции начинается поиск в массиве из семи элементов?

Если элементы пронумерованы от 0 до 6 включительно, первая проверка выполняется на позиции 3. Это четвёртый элемент массива.

Как понять, что число в массиве отсутствует?

Если сравнения сузили диапазон и левая граница стала больше правой, кандидатов больше нет. Этот результат отличается от успешного завершения при равенстве.

Нужна другая тема?

Напишите свою тему или выберите близкую — PREZA подготовит новую презентацию.

Похожие презентации