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

Подумайте о чтении значения в массиве. Компьютер знает, что нужно искать точку в памяти, где хранится элемент. Таким образом, поиск индекса в массиве займет один шаг, так как компьютер может перейти к этой точке в массиве. Теперь давайте посмотрим на линейный поиск в массиве. Компьютер должен просмотреть каждый элемент массива, пока не найдет конкретное значение, которое мы попросили его найти. В зависимости от того, где находится это значение, или если значение не существует в массиве, это может занять столько шагов, сколько длина массива; другими словами, потенциально это может занять N шагов. Это может не иметь большого значения для массива длиной 5, но как насчет массива длиной 100, 200, 1000? Это может начать принимать все больше и больше шагов.

Теперь приходит бинарный поиск. Есть некоторые компромиссы, так как это будет работать только с уже отсортированным массивом. Но понимание того, как это работает и насколько это может быть эффективно, — вот главная мысль, которую я хочу донести. Для небольшого массива, такого как 5, возможно, не самый эффективный поиск. Допустим, в массиве 100 значений, этот поиск теперь занимает всего 7 шагов. Давайте удвоим это количество до 200 значений, этот поиск вырастет до колоссальных 8 шагов. Каждый раз, когда массив удваивается, количество шагов, необходимых для поиска, увеличивается на 1.

Давайте посмотрим, как это ищет в массиве. Бинарный поиск работает путем перехода к средней точке массива и сравнения этого значения со значением, которое мы ищем. Примером может быть массив от 1 до 100, мы просим бинарный поиск искать число 16; поиск переходит к 50 и видит, что 16 меньше 50. В этот момент поиск разрезает массив пополам. Массив для поиска теперь находится в диапазоне от 1 до 49, поскольку он избавляется от верхней половины, а средняя точка поиска равна 24. Компьютер снова видит, что 16 меньше 24; таким образом, массив снова разрезается пополам и теперь составляет от 1 до 23. Эти шаги продолжаются до тех пор, пока поиск не найдет значение или не определит, что значение не существует в массиве. Короче говоря, вы проверяете среднюю точку в массиве и сжимаете окно поиска слева или справа от этой точки в зависимости от значения относительно средней точки. Алгоритм и объяснение смотрите ниже.

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