Бинарный поиск в C++. Подготовил: Студент 2 курса Мишенков Алексей. - презентация

1 Бинарный поиск в C++

2 Содержание Представим код в виде программы 4 Что такое бинарный поиск? 1 Принцип работы бинарного поиска 2 Как создать бинарный поиск в C++ 3 Плюсы и минусы использования бинарного поиска 5

3 Что такое бинарный поиск? Бинарный поиск очень быстрый алгоритм с не сложной реализацией, который находит элемент с определенным значением в уже отсортированном массиве. Очень важно помнить! Алгоритм будет работать правильно, только с отсортированным массивом. А если по случайности вы забыли отсортировать массив перед его использованием, то в большинстве случаев тот ответ, который подсчитал алгоритм, будет неверным.

4 Принцип работы бинарного поиска Допустим, что в нашем распоряжении имеется прибор, который может определить, есть ли бомба в комнате. Необходимо как можно быстрее определить, у кого находится бомба. Самым легким и самым долгим по времени решением, будет поочередная проверка пассажиров в комнате с прибором (это линейный поиск). Но это слишком долго. Давайте сделаем по-другому. Поделим пополам всех пассажиров и разведем их по двум комнатам. Так с помощью прибора мы сможем узнать, в какой из двух комнат находится бомба. В итоге такого маневра мы уменьшим число подозреваемых в два раза. С остальным числом подозреваемых сделаем также: разделим их на две группы и разместим в разных комнатах. Так продолжаем, пока не узнаем у кого бомба. Охранники использовали алгоритм двоичного поиска для нахождения бомбы. В обычной программе принцип работы бинарного поиска такой же.

5

6

7

8 Плюсы и минусы использования бинарного поиска Плюсы: 1. Реализация алгоритма достаточна легкая; 2. Быстрая работа алгоритма; Минусы: 1. Для поиска массив должен быть упорядочен(отсортирован); 2. Двоичный поиск должен иметь возможность обратится к любому элементу данных (по индексу). А это значит, что все структуры данных, которые построены на связных списках использоваться не могут; Совет: использовать бинарный поиск при работе с массивами или векторами. Обычно прогары применяют бинарный поиск с помощью функций.