Алгоритм бинарного поиска числа в списке
Предположим, что вы ищите фамилию в телефонной книге. Она начинается с буквы "К". Конечно можно начать с самого начала и перелистывать каждую страницу в надежде рано или поздно наткнуться на нужную фамилию, но для более рационального поиска лучше раскрыть книгу на середине, ведь нужная нам буква находится где-то ближе к центру книги.
Перед нами типичная задача поиска. В данном случае для решения задачи можно применить алгоритм бинарного поиска.
Рассмотрим пример, как работает данный поиск. Сыграем в игру, я загадал число от 1 до 100 и вы должны его угадать. При каждой попытке вам будет известно больше ли или меньше моё загаданное число по отношению к названному вами. Вы можете начать перебирать все варианты (1, 2, 3, 4, ...) и в худшем случае вы отгадаете число за 99 попыток. Сложность данного аглоритма O(n). Бинарный поск выполняется со сложностью O(log n) и угадать число будет возможно всего за 7 попыток
Предположим, что вы ищите фамилию в телефонной книге. Она начинается с буквы "К". Конечно можно начать с самого начала и перелистывать каждую страницу в надежде рано или поздно наткнуться на нужную фамилию, но для более рационального поиска лучше раскрыть книгу на середине, ведь нужная нам буква находится где-то ближе к центру книги.
Перед нами типичная задача поиска. В данном случае для решения задачи можно применить алгоритм бинарного поиска.
Рассмотрим пример, как работает данный поиск. Сыграем в игру, я загадал число от 1 до 100 и вы должны его угадать. При каждой попытке вам будет известно больше ли или меньше моё загаданное число по отношению к названному вами. Вы можете начать перебирать все варианты (1, 2, 3, 4, ...) и в худшем случае вы отгадаете число за 99 попыток. Сложность данного аглоритма O(n). Бинарный поск выполняется со сложностью O(log n) и угадать число будет возможно всего за 7 попыток