Джефф Льюис

Github:

Примечания:

  • Двоичный поиск ТОЛЬКО работает с отсортированными массивами.

Что такое двоичный поиск?

А. Определение двоичного поиска:

В информатике двоичный поиск (полуинтервальный поиск) - это алгоритм поиска для поиска определенного элемента, расположенного в массиве (ТОЛЬКО работает с отсортированными массивами). Двоичный поиск имеет преимущество перед стандартным линейным поиском, поскольку он выполняет поиск быстрее и эффективнее благодаря тому, что некоторые разработчики называют «разделять и властвовать».

Вместо поиска в массиве с индексами 0, 1, 2, 3, 4 и так далее, как мы делаем в цикле For, двоичный поиск позволяет нам делить наш поиск пополам каждый раз, когда мы ищем целевое значение.

Мы определяем middleIndex или среднюю точку из элемента в середине массива (Divide), чтобы увидеть, больше ли наше целевое значение, чем middleIndex или midpoint. В зависимости от того, больше или меньше целевое значение middleIndex, мы можем удалить левую или правую часть нашего массива из нашего поиска (Conquer).

Б. Двоичный поиск Gif:

В приведенном ниже примере gif мы хотим найти целевое число «37» в этом отсортированном массиве.

С. Пошаговая разбивка процесса двоичного поиска:

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

let exampleArray = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59];
  1. Нам нужно будет отслеживать следующие 3 вещи в качестве переменных для выполнения двоичного поиска: startIndex, middleIndex и endIndex.
  2. startIndex всегда будет 0: let startIndex = 0;
  3. endIndex всегда можно рассчитать с помощью array.length: let endIndex = array.length — 1;
  4. Мы хотим получить начальный middleIndex, используя startIndex и endIndex, и разделить на 2. Это может быть немного сложно из-за четного или нечетного количества элементов в массиве. Мы можем использовать Math.floor() для округления в меньшую сторону или Math.ceil() для округления в большую сторону, но в нашем случае мы собираемся округлить в меньшую сторону с помощью Math.floor(): let middleIndex = Math.floor((startIndex + endIndex) / 2). Это будет единственная индексная переменная, которую мы храним внутри цикла While Loop.
  5. Наш цикл while будет повторять процесс до тех пор, пока не закончится. В нашем случае у меня есть пример с использованием while(startIndex >= endIndex).
  6. Всего в массиве 16 элементов, так что давайте выполним повторную настройку. Мы делим на 2 и округляем в меньшую сторону с помощью Math.floor (), в котором выбирается средний индекс в индексе № 8, где находится число «23». Используя это число «23», мы теперь сравниваем наше целевое число «37», чтобы определить, какие из них больше или меньше друг друга.
  7. Если значение middeIndex меньше целевого значения 37, мы знаем, что наше целевое значение будет где-то справа от middleIndex. Затем мы можем назначить нашу переменную startIndex как текущее значение middleIndex, по существу отрубив левую половину массива. Мы также хотим увеличить middleIndex на 1, если наше целевое число «37» ›middleIndex« 23. »
  8. Если значение middeIndex больше целевого значения 37, мы знаем, что наше целевое значение будет где-то слева от middleIndex. Затем мы можем присвоить нашей переменной endIndex текущее значение middleIndex, по сути отрубив правую половину массива. Мы также хотим уменьшить middleIndex на 1, если наше целевое число «37» ‹middleIndex« 23 »
  9. Если значение middleIndex равно целевому значению 37, мы нашли целевое число «37». Цикл может повторяться только один раз или может повторяться десятки раз, в зависимости от размера вашего массива и вашего целевого числа.
  10. Поздравляем, вы завершили двоичный поиск!

D. Код двоичного поиска:

Приведенный ниже код показывает 2 версии:

1. С комментариями:

const binarySearch = (array, target) => {
  // Define Start and End Index
  let startIndex = 0;
  let endIndex = array.length - 1;
  // While Start Index is less than or equal to End Index
  while(startIndex <= endIndex) {
    // Define Middle Index (This will change when comparing )
    let middleIndex = Math.floor((startIndex + endIndex) / 2);
    // Compare Middle Index with Target for match
    if(target === array[middleIndex]) {
      return console.log("Target was found at index " + middleIndex);
    }
    // Search Right Side Of Array
    if(target > array[middleIndex]) {
      console.log("Searching the right side of Array")
      // Assign Start Index and increase the Index by 1 to narrow search
      startIndex = middleIndex + 1;
    }
    // Search Left Side Of Array
    if(target < array[middleIndex]) {
      // Assign End Index and increase the Index by 1 to narrow search
      console.log("Searching the left side of array")
      endIndex = middleIndex - 1;
    }
    // Not found in this iteration of the loop. Looping again.
    else {
      console.log("Not Found this loop iteration. Looping another iteration.")
    }
  }
  // If Target Is Not Found
  console.log("Target value not found in array");
}

2. Без комментариев:

const binarySearch = (array, target) => {
  let startIndex = 0;
  let endIndex = array.length - 1;
  while(startIndex <= endIndex) {
    let middleIndex = Math.floor((startIndex + endIndex) / 2);
    if(target === array[middleIndex) {
      return console.log("Target was found at index " + middleIndex);
    }
    if(target > array[middleIndex]) {
      console.log("Searching the right side of Array")
      startIndex = middleIndex + 1;
    }
    if(target < array[middleIndex]) {
      console.log("Searching the left side of array")
      endIndex = middleIndex - 1;
    }
    else {
      console.log("Not Found this loop iteration. Looping another iteration.")
    }
  }
  
  console.log("Target value not found in array");
}