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


Итеративный метод Javascript

function binarySearchIterative(arr, x, l, h) {
  while (l <= h) {
    mid = Math.floor((l + h) / 2);

    if (arr[mid] === x) {
      return mid;
    } else {
      if (arr[mid] > x) {
        h = mid - 1;
      } else {
        l = mid + 1;
      }
    }
  }

  return -1;
}
Войти в полноэкранный режим

Выйти из полноэкранного режима


Рекурсивный метод Javascript

function binarySearchRecursive(arr, x, l, h) {
  if (l <= h) {
    mid = Math.floor((l + h) / 2);

    if (arr[mid] === x) {
      return mid;
    } else {
      if (arr[mid] > x) {
        return binarySearchRecursive(arr, x, l, mid - 1);
      } else {
        return binarySearchRecursive(arr, x, mid + 1, h);
      }
    }
  }

  return -1;
}
Войти в полноэкранный режим

Выйти из полноэкранного режима


Объяснение

Функция binarySearch получает четыре параметра: массив, искомое значение xи первый массив low и последняя позиция high.

Мы будем проходить по массиву, пока low меньше или равно high потому что они должны быть на двух концах, если low больше, чем high мы предполагаем, что мы уже прошли интересующую часть массива, и если мы не находим значение, мы возвращаем -1.

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

если среднее значение больше xдело до того, как он станет новым highа если меньше x случае сразу после того, как он становится новым low. Это означает, что интервал будет сокращаться, пока мы не найдем x. Если x нет в массиве, мы возвращаем -1, потому что в какой-то момент low будет больше, чем high и обход будет остановлен.


Иллюстрация

Искомое значение равно 4.

Описание изображения

Сначала мы вычисляем середину массива, которая равна 3. array[3] равно 6, что меньше 4 искомого значения, поэтому мы уменьшаем интервал до того, как 3 станет новым максимумом.

Описание изображения

На втором проходе цикла мы снова вычисляем середину, которая равна 2. массив[2] равно 4, что означает, что мы нашли наш x и затем вернули 2.


Анализ сложности

Поскольку мы никогда не пройдем весь массив, алгоритм бинарного поиска имеет временную сложность О (журнал п) и поскольку мы не используем дополнительное пространство, сложность пространства О(1).


Вывод

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