Если вы новичок в двоичном поиске, я предлагаю вам прочитать мою предыдущую запись в блоге «Серии алгоритмов - двоичный поиск», прежде чем читать эту статью.

Задача кодирования

Реализуйте двоичный поиск в массиве [2, 5, 6, 9, 13, 15, 28, 30], чтобы найти значение 15.

Псевдокод

Для работы двоичного поиска нам нужен отсортированный массив. Сортировка означает, что она упорядочена - это применимо также к строкам (A ‹B‹ C), а не только к числам. Массив в нашей задаче отсортирован от самого низкого до самого высокого, поэтому это предварительное условие выполнено. В нашем массиве мы должны создать три указателя: левый указатель в начале, правый указатель в конце и средний указатель в середине (да). В крайних случаях (например, когда мы ищем значение, которого нет в массиве), может случиться так, что указатели пересекаются (подробнее об этом позже), что приведет к нежелательным результатам, таким как бесконечные циклы. Итак, что мы делаем:

Пока левый указатель находится перед правым указателем…

  • Создайте средний указатель (возьмите среднее значение индекса)
  • Если найдете значение, верните индекс
  • Если значение меньше среднего, переместите правый указатель вниз
  • Если значение больше, чем значение в середине, переместите левый указатель вверх
  • Если вы никогда не найдете значение, верните -1

Реализация кода

Работаем с индексами. Начало (левый указатель) - это индекс 0, конец (правый указатель) - это индекс 7. Длина равна количеству значений в нашем массиве, которое равно 8, но нет 8-го индекса (потому что они начинаются с 0). Последнее значение в нашем массиве - 30, что находится в индексе 7, поэтому мы вычитаем 1 из длины нашего массива, чтобы получить правильный индекс для конца. Среднее значение 7 = 3,5, и у нас, очевидно, нет значения в индексе 3,5. В нашей реализации мы решили округлить с помощью Math.floor, но это вполне нормально с помощью Math.ceil. Единственное, что здесь важно, - это соответствовать тому, что вы решили выбрать. Поскольку мы округлили в меньшую сторону, наша средняя точка - index = 3, что равно значению 9.

В условии while мы проверяем, соответствует ли значение в среднем индексе искомому элементу, а именно 15. Хотя значение в среднем индексе не соответствует искомому значению, мы проверяем, соответствует ли элемент, который мы ищем, ищите меньше, чем значение в среднем индексе. Если это так, мы сдвигаем конечную точку на один индекс влево к середине, а если это не так (если значение, которое мы ищем, больше, чем значение в среднем индексе), мы сдвигаем начальную точку на один индекс вправо середина. Впоследствии рассчитываем новую среднюю точку. Наш чек…

while(arr[middle] !== elem)

… Равняется истине на нашем начальном SME, потому что значение, которое мы ищем, не равно значению в среднем индексе.

Затем нам нужен либо новый начальный индекс (если значение, которое мы ищем, больше средней точки), либо новый конечный индекс (если значение, которое мы ищем, меньше средней точки). Поскольку мы ищем 15, попадаем в блок else:

else {
 start = middle + 1;
 }

Здесь мы устанавливаем новую начальную точку. После…

middle = Math.floor((start + end) / 2);
​ ​ ​​​ ​​ ​​​ ​ ​​ ​ ​​​ ​ ​​ ​ ​​​ ​ ​

… Мы создаем новую среднюю точку, которая не связана с if-else, потому что, если значение, которое мы ищем, не было в нашем начальном среднем индексе (поэтому, если оператор while равен true), нам придется создать новая средняя точка независимо от того, больше или меньше искомое значение, чем значение в средней точке. Почему 15 - средняя точка? Помните, мы работаем с индексами. Новый начальный индекс равен 4 (значение 13), а конечный индекс по-прежнему равен 7 (значение 30). Сумма индексов равна 11, а среднее значение 11 равно 5,5. Поскольку вначале мы округляли в меньшую сторону, наша продолжающаяся практика дает нам среднюю точку 5, где стоит число 15. И это номер, который мы искали. Мы нашли это! Давайте немного усложним задачу и поищем число 28. Как будет выглядеть следующая итерация?

Если вы правильно предсказали, поздравляем! Если нет, помните:

else {
 start = middle + 1;
 }

Начальная точка сбрасывается и теперь равна средней точке + 1 (то есть 28). Середина равна среднему индексу (duh) начальной точки плюс индекс конечной точки, то есть индекс 6 + индекс 7 = 13. Середина индекса 13 равна 6,5, и мы округляем его до 6, что равняется значению 28. Итак, теперь начальная и средняя точки находятся в одном месте, а конечная точка не перемещается. И мы нашли свою ценность! Давайте протестируем наш код:

Однако с нашим кодом есть одна большая проблема: он на самом деле не работает. Это означает, что это не работает с определенным пограничным случаем - если мы ищем значение, которого нет в массиве, что происходит?

После второй итерации новой начальной точкой будет средняя точка + 1, то есть индекс 7. Таким образом, начальная и конечная точки имеют индекс 7, и если мы сложим оба индекса и уменьшим результат вдвое, мы получим новую середину. точка индекса 7. Третья итерация затем найдет все точки - начало, середину и конец - на 30. Но так как мы все еще не нашли 50, мы повторяем снова. Однако теперь начальный индекс равен 8, что находится за пределами допустимого диапазона. Начальная точка затмила конечную точку, пересекла. Средняя точка не перемещается, так как индекс 8 + 7 = 15, деленный на два и округленный в меньшую сторону, мы все равно получаем 7. Во время следующего цикла начальная точка устанавливается равной средней точке + 1, которая по-прежнему равна 8. Это означает, что все наши точки застряли и не сдвинутся с места. Мы находимся в бесконечном цикле, из которого нам нужно выбраться.

while(arr[middle] !== elem) && start <= end)

Теперь мы реализовали способ выхода из бесконечного цикла. Мы указали еще одно условие, которое должно быть истинным для запуска цикла while. Когда наша начальная точка затмевает нашу конечную точку, цикл while прекращается, и функция возвращает средний индекс:

Ура! Есть хорошие и плохие новости: хотя нам удалось выйти из бесконечного цикла, мы возвращаем неправильный индекс! Однако это легко решить с помощью дополнительной строки кода:

В последней строке мы говорим: «Если значение в индексе средней точки в массиве равно элементу, вернуть средний индекс, в противном случае вернуть -1».

Надеюсь, это было понятно :) Если у вас есть вопросы, не стесняйтесь их спрашивать! (: