Привет, добро пожаловать в другой раздел WTF: is *Blank*, сегодня мы собираемся обсудить, что такое Двоичный поиск. Существует несколько способов поиска определенного элемента (целого числа, строки и т. д.) в заданном массиве, и одним из таких способов является двоичный поиск, который, по сути, разрезает массив по мере того, как мы перебираем его. Итак, приступим!
Введение:
Двоичный поиск — это один из основных алгоритмов поиска, которые вы изучаете при изучении программирования. По сути, он разбивает часть массива, которую нам не нужно перебирать по мере продвижения, поэтому в конце поиска мы остаемся с желаемым результатом. При бинарном поиске следует помнить, что он только работает с отсортированными массивами. Теперь, когда это не так, давайте узнаем, как реализовать бинарный поиск. Я буду использовать JavaScript, но вы можете закодировать его на любом другом языке, поскольку концепция остается прежней.
Выполнение:
Во-первых, наша функция будет принимать два аргумента: входной массив 'arr', который нужно найти, и элемент 'target', который нам нужно найти во входном массиве.
Теперь давайте создадим три переменные, start,middle, и end, которые будут действовать как указатели (индикаторы) для первого, среднего и последнего элемента массива соответственно.
Указатель start может быть указан как индекс 0 массива, а конечныйуказатель может быть на единицу меньше, чем длина массива, которая в конечном итоге равна последний элемент. Для указателя middle мы можем найти среднее значение указателя start и end и преобразовать его в целое число (на случай, если он окажется равным поплавок).
Теперь, когда у нас есть указатели, давайте напишем самое интересное;
Мы начнем с написания цикла, который сравнивает наше значение arr[middle] в массиве с нашим значением target, если нам повезет, мы можем получить нашу цель значение без запуска цикла. В любом случае, если arr[middle] не является нашим целевым значением, мы проверяем, больше или меньше это среднее значение, чем наше целевое значение.
В случае, когда наше среднее значение больше, мы переключаем наш конечный указатель на единицу меньше, чем наш средний ( end = middle - 1 ), потому что теперь мы знаем, что наша цель находится где-то в этих элементах. То же самое происходит, когда наше среднее значение меньше нашего целевого, тогда мы переключаем наш начальный указатель так, чтобы он был на единицу больше, чем наше среднее значение ( start = middle + 1 ).
Теперь, поскольку у нас есть новый начальный или конечный индекс, нам нужен новый средний индекс, поэтому мы повторяем то же самое, что и раньше: берем среднее значение начального и конечного указателя, а затем округляем его до ближайшего целого числа. В конце цикла мы продолжаем проверять, равно ли наше среднее значение нашему целевому значению, которое, если true, вернет нам средний индекс, в противном случае цикл продолжится.
Но что произойдет, если целевое значение не находится в массиве? Что ж, наша текущая программа будет продолжать цикл до бесконечности, поэтому для решения этой проблемы нам просто нужно добавить еще одно условие в наш цикл while;
В цикле while мы проверяем, меньше ли наш начальный указатель, чем наш конечный указатель, потому что в случае, если это утверждение false, это означает, что наш цикл прошел вне массива, что приводит к отсутствию целевого значения, и то же самое происходит, если конечный указатель меньше начального указателя.
Вот и все, мы реализовали простой алгоритм бинарного поиска.
Привет! Спасибо, что дошли до конца этого поста. Если он вам понравился или у вас есть какие-либо вопросы, не стесняйтесь комментировать!
