Пошаговый пример получения скорости O (log n) для вашей итерации

Допустим, я дал вам словарь и попросил найти определение для поиска. Затем я попросил вас дать определение двоичного файла . Вы бы начали примерно с одной и той же страницы для обоих?

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

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

Представьте, что у нас есть отсортированный массив целых чисел, и нам нужно написать функцию, которая сообщает нам, есть ли в нем заданное целое число, скажем, счастливое число 7, или нет:

arr = [1, 2, 4, 5, 7, 8, 9]

Мы ясно видим, что это так. А простой цикл for в конечном итоге достигнет 7 и вернет true. Но что, если бы мы хотели сделать это быстрее, потому что массив был огромным?

Давайте объявим функцию iterativeBinarySearch, которая принимает наш массив и число, которое мы ищем. Давайте также объявим две переменные, которые помогут нам в нашей задаче:

function iterativeBinarySearch(arr, n) {
  let start = 0;
  let end = arr.length - 1;
}

Мы инициализируем start с 0 и end независимо от длины массива минус 1 . Эти две переменные-указатели будут представлять, где мы хотим, чтобы наш алгоритм фокусировался (как бы говоря) при выполнении итерации. Затем мы вводим цикл while и сразу же инициализируем третью переменную, которая представляет собой середину между начальной и конечной точками:

function iterativeBinarySearch(n, arr) {
  let start = 0;
  let end = arr.length - 1;
while (start <= end) {
    let mid = Math.floor((start + end) / 2);
  }
}

Mid в этот момент равно 3, потому что (0 + 6) / 2 = 3. Часть math.floor предназначена для учета неравномерных случаев. Он будет округляться в меньшую сторону. Затем мы немедленно начинаем искать наше введенное число, в данном случае 7:

if (arr[mid] === n) {
      return true;
    }

Поскольку arr [3] = 5, что 7, мы не возвращаем true. Нам понадобится еще:

else if (arr[mid] < n) {
      start = mid + 1;
    }

Поскольку arr [mid] = 5, а 5 меньше 7, этот оператор принимает значение true и повторно присваивает значение start 4.

Здесь начинается мощь двоичного поиска.

Если мы знаем, что середина того, что мы ищем, меньше, чем то, что мы ищем, зачем нам снова возвращаться к началу? Начнем с середины плюс один.

Теперь мы вернулись во время цикла while. Мы объявляем mid равным (3 + 1 + 6) / 2 = 5

  • Поскольку arr [5] = 8 7, мы не возвращаем true.
  • Поскольку arr [5] = 8 не меньше 7, мы также не возвращаем true. Но и своего номера мы не нашли. Оказывается, нам нужен еще один оператор else:
else {
      end = mid - 1;
    }

Как и раньше, если мы знаем, что массив в средней точке больше искомого числа, зачем нам снова смотреть дальше этой точки? Сделаем конец на единицу меньше середины. Итак, теперь мы делаем end 5–1 = 4.

Снова входим в петлю. Теперь наша средняя точка равна (4 + 4) / 2 = 4.

Поскольку arr [4] = 7, это число, которое мы ищем, выражение теперь принимает значение истина, и мы возвращаем истину. Вот полный код для справки:

function iterativeBinarySearch(n, arr) {
  let start = 0;
  let end = arr.length - 1;
while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === n) {
      return true;
    } else if (arr[mid] < n) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return false;
}

Мы нашли наше число всего за 3 итерации, в отличие от 4, которые были бы при обычном цикле for, который выполняется за линейное время - O (n). С таким маленьким массивом эта разница тривиальна. Но если бы наш массив был гигантским, непрерывное сокращение пространства, которое мы должны просматривать, пополам, может иметь существенное значение. Этот факт представлен на графике ниже: по мере увеличения размера объекта разница между решением O (n) (зеленая линия) и решением O (log n) (красная линия) увеличивается. Но при низком n, таком как в нашем примере, разница, если она есть, незначительна.

Спасибо за прочтение!

И помните: выдержка ›талант.