Алгоритм поиска. Бинарный поиск

1.

АЛГОРИТМ ПОИСКА:
БИНАРНЫЙ ПОИСК
Подготовил: ДахноК.К.

2.

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

3.

Принцип бинарного поиска:
■ 1. Сортируем массив данных.
■ 2. Делим его пополам и находим середину.
■ 3. Сравниваем срединный элемент с заданным искомым элементом.
■ 4. Если искомое число больше среднего — продолжаем поиск в правой части
массива (если он отсортирован по возрастанию): делим ее пополам, повторяя
пункт 3. Если же заданное число меньше — алгоритм продолжит поиск в левой
части массива, снова возвращаясь к пункту 3.

4.

Пример использования бинарного
поиска:
■ Найти индекс элемента 42 в отсортированном массиве.
■ Массив: [10, 20, 30, 40, 42, 50, 60, 70]
■ Шаги: 1) Начальные границы: (0, 7)
■ 2) Средний элемент: 40 (меньше 42)
■ 3) Новые границы: (4, 7)
■ 4) Средний элемент: 50 (больше 42)
■ 5) Новые границы: (4, 5)
■ 6) Средний элемент: 42 (искомый элемент найден)
■ 7) Результат: Индекс элемента 42: 4

5.

Вывод:
■ Бинарный поиск – мощный алгоритм поиска, особенно эффективный в
отсортированных данных. Его принцип работы основан на разделении
пространства поиска пополам на каждом шаге, что позволяет быстро сузить
диапазон и находить искомый элемент. Пример использования в
отсортированном массиве демонстрирует эффективность алгоритма, позволяя
быстро найти искомый элемент.