Бинарный поиск

Такой алгоритм применяется для задач поиска, например: мы ищем значение слова на букву К в словаре. Возникает несколько вариантов: открыть словарь с начала и листать до буквы К, а есть вариант открыть словарь где-нибудь в середине, ведь буква К ближе к ней.

Алгоритм:

① Определяем значение элемента в середине структуры данных, полученное значение сравниваем с ключом

② Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, больше — во второй

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

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

При бинарном поиске на каждом этапе исключается половина значений, такой алгоритм очень эффективен!