Когда я начал погружаться в глубокий и сложный мир информатики, я был очень напуган тем, что было передо мной, и огромной глубиной всего этого. Одним из первых, о чем я узнал, был алгоритм двоичного поиска.
Вы видите, когда мы пишем алгоритмы или наборы инструкций для работы нашего компьютера, в идеале мы хотим, чтобы он работал как можно эффективнее и быстрее. Одним из примеров может быть алгоритм поиска. Для наших целей алгоритм будет просто запросом одного элемента внутри отсортированной коллекции. Хороший пример - запрос телефонной книги. Вы ищете человека в телефонной книге и надеетесь, что это имя существует в телефонной книге. Если человек действительно существует в телефонной книге, значит, у вас есть его номер телефона или должность в книге. Есть два способа сделать это; простой поиск или с помощью нашего нового инструмента, двоичного поиска.
Начнем с простого поиска. Если бы у вас не было ограничений по времени и вы не знали, как найти этого человека в этом гигантском своде записей. Вам придется перебирать каждый элемент коллекции по одному, пока вы не найдете человека, которого ищете…. Это было бы ужасно, шансы, что вы вовремя найдете этого человека, ничтожны. В лучшем случае это может быть первый человек или человек может быть на первых нескольких страницах, но в худшем случае это может быть последний человек на странице ПОСЛЕДНЯЯ. Так что это действительно витает в воздухе, и чем больше набор элементов, тем больше времени потребуется на выполнение запроса. Вот фрагмент кода, чтобы проиллюстрировать, как это происходит
А теперь попробуем бинарный поиск. При двоичном поиске ключом является отсортированная коллекция. С сортировкой по коллекции двоичный поиск действительно выглядит как лучший способ найти человека в телефонной книге. С помощью двоичного поиска вы угадываете средний номер или элемент в коллекции и удаляете половину коллекции, независимо от того, был ли элемент слишком большим или слишком маленьким. Затем вы повторяете процесс и непрерывно сужаете коллекцию, угадывая новый средний элемент во вновь сокращенной коллекции и сужая ее, пока не найдете элемент и положение в коллекции.
Вот фрагмент кода:
Кажется, что многое происходит, но с помощью этого метода вы на самом деле значительно упрощаете поиск того, что ищете, и находите это в рекордно короткие сроки. Вы назначаете низкое и высокое значение и последовательно меняете их по мере уменьшения коллекции и в результате назначаете новое среднее значение. Затем вы проверяете, совпадает ли это новое среднее значение с искомым элементом, и возвращаете среднее значение. В противном случае переназначьте новые высокие, низкие и средние значения и начните заново. Отсортированная коллекция позволяет легко переназначать новое среднее значение каждый раз.
Теперь, когда вы познакомились с обоими методами, я надеюсь, что если вам нужно написать простой алгоритм поиска, вы будете делать это с помощью двоичного поиска, а не просматривать каждый элемент по одному.
