Алгоритм двоичного поиска в Javascript

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

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

Интересный факт:

«Если все имена в мире записаны вместе по порядку, и вы хотите найти позицию определенного имени, двоичный поиск выполнит это максимум за 35 итераций». (Hackerearth.com)

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

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

Также рекомендуется определять функции, которые сосредоточены на одной цели. Будет разумнее определить функцию для сортировки, а затем вызвать функцию двоичного поиска для поиска.

Прежде чем погрузиться в код, давайте пройдемся по этапам двоичного поиска.

1. Найдите начальную и конечную точки массива, часто называемые минимумом и максимумом. Низким будет индекс 0, высоким будет размер массива минус 1. В информатике мы считаем индекс от 0 и элементы от 1, поэтому последний индекс массива часто будет равен n минус 1, где n - размер. массива.

2. Найдите медиану массива. Это можно сделать, выполнив (низкий + высокий) / 2.

3. Сравните цель поиска с медианой, если они совпадают, мы нашли цель и просто возвращаем индекс. Это также называют лучшим случаем.

4. Если цель меньше медианы, это означает, что все, что больше медианы, также будет больше цели, поэтому мы можем пренебречь этим. Мы делаем это, уменьшая индекс верхней границы, обновляя его до медианы минус 1, потому что медиана также сравнивалась и ею можно пренебречь.

5. Точно так же, если цель больше медианы, мы увеличим нижнюю границу, обновим ее до медианы + 1.

6. Повторяйте вышеуказанные шаги до тех пор, пока цель не будет найдена или не будут проверены все числа.

Теперь давайте посмотрим на следующий пример:

Мы пытаемся найти 5 и получаем его позицию в индексе, если он найден:

Первая итерация:

Размер массива = 13

низкий = 0

высокий = 13–1 = 12

середина = (0 + 13) / 2 = 6

цель = 5

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

Теперь для второй итерации будет обновлено максимальное значение, поскольку мы пренебрегаем данными, которые равны или больше медианы.

2-я итерация:

высокий = 6–1 = 5

низкий = 0

середина = (0 + 5) / 2 = 2

Цель меньше медианы, пренебречь второй половиной, обновить максимальное значение.

3-я итерация:

низкий = 0

высокий = 3–1 = 2

середина = (0 + 2) / 2 = 1

array [mid] = 5, который является нашей целью, поэтому будет возвращен индекс 1.

Вот еще один пример:

Теперь перейдем к коду:

function BinarySearch(array, low, high, target)
{
  //base condition
  // To exit the recursion, if array is empty or n = 1
  if(low > high) {
    return -1;
  }
  //calculate the midpoint of array
  let mid=Math.floor( (low+ high)/2) ;

  if (target == array[mid]) {
    console.log('Target is found at index: ', mid)
    return mid;
  }
  else if (target < array[mid]) {
  //if the target is less the number at the midpoint of array
  //Search the 2nd half. 
    return BinarySearch(array, low, mid-1, target);
  }
  else {
  //if the target is larger number at the midpoint of array
  //Search the 1st half.
    return BinarySearch(array, mid+1, high, target);
  }
}

// To test:
BinarySearch([1,5,7,8,9,10,15], 0, 6, 5)
// Console:
'Target is found at index:  1'

Сложность выполнения двоичного поиска составляет O (logn), потому что размер данных уменьшается вдвое на каждой итерации.

На итерации 1 длина массива = n,

итерация 2, n = n / 2

итерация 3, n = (n / 2) / 2

После итерации k длина массива станет n / 2 ^ k.

Если вас интересует временная сложность, перейдите по этой ссылке:

Https://www.geeksforgeeks.org/complexity-analysis-of-binary-search/

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

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