Как программист, вы будете постоянно сталкиваться с такой проблемой…
"Эй, помнишь тот массив, в котором ты хранишь кучу важных значений? Здорово! Что ж… теперь мне нужно, чтобы вы нашли X, и убедитесь, что вы нашли его как можно быстрее!»
Именно по этой причине важно изучать алгоритмы поиска для программиста! Вы никогда не узнаете, когда вам нужно выполнить поиск в вашем массиве, поэтому, если вы когда-нибудь столкнетесь с такой проблемой, вы будете знать, что делать.
Давайте вместе разберемся с простым алгоритмом поиска:
«Я хочу, чтобы вы нашли число 99 в этом массиве случайных чисел, который у меня есть по порядку. Я даже не уверен, есть ли там 99, но если да, то дайте мне знать!»
Вот массив, в котором мы ищем:
[1, 3, 5, 12, 16, 24, 25, 27, 33, 37, 42, 45, 50, 53, 56, 64, 65, 77, 80, 83, 86, 89, 99, 112]
…итак, давайте подумаем над этой проблемой. Очевидная стратегия состоит в том, чтобы просто перебирать массив, начиная с первого индекса, поднимаясь один за другим, пока не встретим наше число 99. Это так называемый линейный поиск. Давайте реализуем эту стратегию:
- Я создал функцию linearSearch, которая принимает массив и targetValue.
- Я инициализировал цикл for, который повторяется до тех пор, пока i не станет меньше длины передаваемого массива.
- В каждом цикле я проверяю, равен ли массив по индексу i (array[i]) targetValue прошёл.
- Если числа совпадают, поздравляем, мы нашли!
- Если числа не равны, то цикл повторяется
- Если выполняется поиск по всему массиву, мы возвращаем false и говорим, что не можем найти targetValue (его нет в массив)
Как вы можете видеть в моих тестах под функцией, я ищу число 99,которое действительно находится внутри массива, поэтому значение 99 вернулся ко мне!
Что касается моего второго теста, я ищу число 22, которое не находится внутри массива, поэтому мне говорят, что функция не может найти мой номер.
Хотя это и рабочая стратегия, она не самая эффективная, и вот почему.
Как вы можете заметить, взглянув на наш массив, 99 находится в конце массива, а это означает, что нам пришлось просматривать почти каждый index массива до того, как мы нашли наше targetValue! Должен быть лучший способ!
Входит бинарный поиск
Бинарный поиск
Двоичный поиск — это алгоритм, в котором мы ищем в отсортированном списке элементов. Стратегия этого алгоритма состоит в том, чтобы делить список пополам при каждом предположении, чтобы сузить возможные варианты нашего targetValue.
Давайте используем наш пример проблемы выше для этой реализации поиска. у нас все еще есть тот же массив чисел:
[1, 3, 5, 12, 16, 24, 25, 27, 33, 37, 42, 45, 50, 53, 56, 64, 65, 77, 80, 83, 86, 89, 99, 112]
Давайте напишем способ решения этой проблемы.
- Мы хотим иметь минимальное значение и максимальное значение. min будет равно нулю, а max будет равной длине массива-1.
- Нам нужно разделить массив пополам, как в настоящей функции бинарного поиска! Мы можем использовать наши значения min и max, чтобы помочь! Чтобы найти центр массива, нам нужно найти среднее значение длины массивов: (min + max)/2. Наше среднее не всегда может быть целым числом, поэтому мы округлим его в меньшую сторону. Это число будет нашим угадыванием!
- Используя нашу догадку, мы сначала хотим проверить, правильно ли мы угадали! (массив[догадка] === целевое значение)
- Если предположение меньше, чем targetValue (array[guess] ‹ targetValue), нам нужно увеличить наше предположение. Помните, что предположение — это среднее значение min и max, так как же увеличить среднее значение? Увеличивая мин! Мы хотим установить min равным нашей догадке + 1.
- Если догадка больше, чем targetValue, т. е. противоположно тому, что объяснено в пункте 4, тогда мы захотим уменьшить значение max: макс. = предположение-1
- Повторить с шага №2
Если вы запустите это, включая тестовую задачу внизу, вы должны получить 99 за 5 предположений, то есть мы проверим только 4 числа, прежде чем доберемся до нашего targetValue! Это намного эффективнее, чем проверка всех остальных чисел в массиве. Если бы у нас был массив длиной 100, наш компьютер непременно поблагодарил бы нас за использование алгоритма бинарного поиска!
Я надеюсь, что теперь вы видите пользу в понимании алгоритма бинарного поиска, и я надеюсь, что эта статья оказалась для вас полезной. Удачного кодирования!
