Понимание бинарного поиска

Как указано в первом уроке книги «Понимание алгоритмов», мы должны создать двоичный поиск, который использует метод «разделяй, чтобы победить», чтобы найти число внутри массива наиболее эффективным способом.

Как указано в первом уроке книги «Понимание алгоритмов», мы должны создать бинарный поиск, объяснив контекст: что такое бинарный поиск?

Есть ситуация, которая может помочь вам найти его: допустим, у вас есть книга из 5000 страниц, и вы хотите найти в ней определенную страницу. Давайте представим, что вы ищете страницу 487.ria, которая использует метод «разделяй, чтобы победить», чтобы найти число внутри массива наиболее эффективным способом.

Чтобы найти страницу 487, вы можете использовать несколько методов, один эффективнее другого:

Простой поиск

Простой метод поиска просматривает книгу страница за страницей, пока не найдете страницу 487. Учитывая, что вы тратите 1 секунду на страницу, вам потребуется 487 секунд, чтобы найти страницу.

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

Метод бинарного поиска — это способ найти страницу наиболее оптимизированным способом. с помощью этого метода вы бы разделили книгу из 5000 страниц пополам, то есть вы бы открыли книгу на странице 2500 и задали бы себе следующий вопрос: «Страница, которую я хочу, находится до или после середины книги?»

Если ваш ответ «после», вы начнете поиск конкретной страницы с 2500 страницы книги,

Если ответ «до», вы начинаете поиск конкретной страницы от 0 до 2499.

Смотрите на практике:

Когда мы сравним два времени выполнения простого и бинарного поиска, мы заметим, что при небольших числах простой поиск может дать более быстрые результаты, но в какой степени?

Чтобы выяснить это, давайте проведем несколько тестов.

Сравнительные

Теперь давайте возьмем книгу из 50 000 страниц, и выбранная страница будет случайной.

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

Базовый поиск:

Случайная страница в книге на 500 000 страниц

*здесь мы уже начинаем замечать разницу

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

Базовый поиск:

Случайная страница в книге из 5 000 000 страниц

*большая разница во времени

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

Базовый поиск:

Последние мысли

Двоичный поиск — это одна из стратегий, которую вы можете использовать, когда вам нужно найти что-то конкретное в огромной коллекции других объектов.

Даже в повседневных ситуациях использование бинарного поиска имеет большой смысл.

Но также важно следующее наблюдение: если вы новичок и впервые сталкиваетесь с оптимизацией и перформативными операциями BigO, важно, чтобы вы знали, что бинарный поиск — это НЕ панацея.

Это занимает некоторое время, так как имеет смысл использовать бинарный поиск вместо базового поиска, и, скорее всего, он не понадобится вашим бэкэнд-проектам, как это уже делают многие используемые вами фреймворки.