Эпоха 90-х.
Если вы помните что такое телефонная книга, то вам минимум 25-30 лет :). Для всех остальных картинка с описанием ниже.
Не зря я начал именно с примера о телефонной книге.
Как найти номер человека, фамилия которого начинается на букву "М" ?
И так, в русском алфавите 33 буквы, фамилии на букву "М" должны быть примерно по середине справочника, верно? Открываем справочник на середине и видим букву "К", всё что слева мы "отрываем", теперь у нас в два раза меньше вариантов, далее снова "отрываем" половину и вариантов ещё в 2 раза меньше и до тех пор пока не найдём искомую фамилию на букву "М". Быстрее чем листать с самого начала, не так ли?
- Перейдём к цифрам.
Предположим в нашем справочнике 100 000 фамилий с номерами.
Мы ищем фамилию "Маврин". Используя способ "отрывания" за сколько шагов мы найдём то что искали?
100 000 -> 50 000 -> 25 000 -> 12 500 -> 6 250 -> 3 125 -> 1 563 -> 782 -> 391 -> 196 -> 98 -> 49 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1
Как вы уже догадались, каждый раз я делил цифру на 2, округляя в большую сторону и получил 17 шагов.
А это значит одно, чтобы найти "Маврина" или "Швабрина" нам потребуется не более 17 шагов!
А теперь напишите в комментариях, сколько бы потребовалось шагов, если искать с самого начала?
Возвращаемся в нашу эпоху.
Instagram, ВКОНТАКТЕ, Одноклассники, Facebook - что их объединяет?
Правильно, база данных. Несколько сотен миллиардов пользователей, чтобы зарегистрироваться в той или иной соцсети сейчас нужно выбрать уникальное имя, которого ещё нет в базе. И для того чтобы сравнить введённое вами имя используется так называемый "бинарный поиск".
Вы уже представили что бы было, если искать без "отрывания" ?
Примерно такое: "Пожалуйста, подождите 10 дней, пока мы проверим введённое имя пользователя в нашей базе"
В следующей части разберёмся в чём математическое отличие смысла двух подходов к поиску и напишем первую программу, используя язык Python.