Адитья Бхаргава. Грокаем алгоритмы. Конспект книги с примерами реализации алгоритмов на java script.

Глава 1. Знакомство с алгоритмами

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

Алгоритм на входе получает отсортированный список элементов. Возвращает позицию искомого элемента или null.

Пример: игра "угадай число". Загадано число от 1 до 100. При каждой попытке возвращается ответ: "мало", "много" или "угадал". Плохой способ – перебирать все числа подряд. При самом отрицательном сценарии потребуется 100 попыток. Эффективный способ – начнем с 50. Если мало, то пробуем 75. Если много, то 63 и тд, каждый раз исключая половину оставшихся возможных вариантов. Какое бы число не было задумано, его можно угадать не более чем за 7 попыток.

При простом поиске из 240 000 вариантов может потребоваться 240 000 попыток. При бинарном - максимум 18. Для списка из n элементов простой поиск занимает n шагов, бинарный log2n шагов.

Логарифм по смыслу противоположен возведению в степень. Логарифм по основанию 10 от 100 означает в какую степень нужно возвести 10, чтобы получить 100. Ответ 10

В нотации "О большое"(об этом позже), log всегда означает 2. Для списка из 8 элементов log8 == 3, тк 2^3 === 8.

Бинарный поиск работает только с отсортированным списком.

Время выполнения

Скорость измеряется не временем, а ростом кол-ва операций.

Если максимальное к-во попыток совпадает с размером списка, при простом поиске, время выполнения - линейное время пыполнения.

При бинарном поиске - поиск выполняется за логарифмическое время.

Факториальное время - ужасный ужас - при очень длинном списке, поиск становится невероятно долгим. Наример, поиск кратчайшего расстояния для того, чтобы объехать n городов: 5 городов - 120 операций, 6 городов - 720, 7 городов - 5040.

линейное время - O(n) логарифмическое время - O(log n) факториальное время - O(n!)

Реализация бинарного поиска Упражнения