Двоичный поиск — это быстрый и эффективный алгоритм, используемый для поиска элемента в отсортированном массиве. В этой статье мы обсудим, как реализовать бинарный поиск в JavaScript, используя как цикл, так и рекурсию. Мы пройдемся по процессу и сравним реализацию друг с другом. его статья предоставит ценную информацию о реализации бинарного поиска.

Это лишь одна из многих статей об ИТ. Мы разбиваем сложные темы на небольшие и удобоваримые для вас содержания. Не стесняйтесь подписаться или поддержать pandaquests, чтобы получить больше интересного контента о JavaScript, веб-разработке и разработке программного обеспечения. Мы стараемся публиковаться несколько раз в неделю. Не пропустите ни одного из наших замечательных материалов.

Двоичный поиск — это алгоритм поиска, используемый для нахождения позиции элемента в отсортированном массиве. Он работает, разделяя массив на две части и сравнивая средний элемент массива с целевым элементом. Если средний элемент равен целевому, поиск завершается успешно и возвращается индекс среднего элемента. Если средний элемент меньше целевого, поиск продолжается в правой половине массива. Если средний элемент больше целевого, поиск продолжается в левой половине массива. Этот процесс продолжается до тех пор, пока цель не будет найдена или пока не будет определено, что цель отсутствует в массиве.

Это эффективный алгоритм поиска с временной сложностью O(log n), где n — количество элементов в массиве. Это означает, что по мере увеличения размера массива количество итераций, необходимых для поиска цели, уменьшается. Это делает бинарный поиск хорошим выбором для больших массивов, где нужно быстро найти целевой элемент.

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

Циклы в JavaScript — это способ повторения блока кода заданное количество раз или до тех пор, пока не будет выполнено определенное условие. В JavaScript есть разные типы циклов: циклы for, циклы for...of, циклы for...in и циклы while. Они позволяют перебирать массивы, объекты и другие структуры данных для многократного выполнения определенной задачи.

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

Вот пример реализации бинарного поиска с циклом:

const binarySearch = (array, target) => {
  let left = 0;
  let right = array.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (array[mid] === target) return mid;
    if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
};
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const result = binarySearch(arr, 6);
console.log(result); // 5

А вот пример с использованием рекурсии:

const binarySearch = (array, target, left = 0, right = array.length - 1) => {
  if (left > right) return -1;
  
  const mid = Math.floor((left + right) / 2);
  if (array[mid] === target) return mid;
  if (array[mid] < target) {
    return binarySearch(array, target, mid + 1, right);
  }
  return binarySearch(array, target, left, mid - 1);
};
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const result = binarySearch(arr, 6);
console.log(result); // 5

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

Что касается приведенных выше примеров, первая реализация кода использует цикл while для итерации по массиву, обновляя значения left и right до тех пор, пока цель не будет найдена или не будет определено, что цель не существует в массиве.

Вторая реализация кода использует рекурсию для решения проблемы. Базовый случай рекурсии — когда left больше, чем right, и в этом случае функция возвращает -1. Если цель найдена, функция возвращает ее индекс. Если цель не найдена, функция продолжает вызывать себя с обновленными значениями left и right, пока не будет достигнут базовый случай.

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

Вот оно. Надеемся, вам понравилась эта статья. Если да, пожалуйста, аплодируйте, подписывайтесь и делитесь. Это бы нам очень помогло. Есть вопросы? Дайте нам знать и прокомментируйте ниже.

Мы публикуем несколько статей в неделю. Мы разбиваем сложные темы на небольшие и удобоваримые для вас материалы. Чтобы не пропустить ни одного из них, следите и подписывайтесь на pandaquests. Если вы хотите поддержать нас напрямую, вы можете либо дать чаевые, либо подать заявку на членство по этой ссылке. Используя эту ссылку, 50% вашего вознаграждения перейдет непосредственно к нам. Только благодаря вашей щедрой поддержке мы сможем сохранить частые и качественные наши статьи. Заранее спасибо и удачного кодирования!

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .

Заинтересованы в масштабировании запуска вашего программного обеспечения? Ознакомьтесь с разделом Схема.