Линейный поиск

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

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

Таким образом, в среднем необходимо проверить половину значений в массиве, чтобы найти искомое значение. Чтобы убедиться, в отсутствии искомого значения необходимо проверить все элементы массива. Разработаем программу, которая ищет минимальное значение в массиве. Поиск в программе реализован согласно алгоритму линейного поиска в массиве.

const array = [6, 5, 8, 21, 1, 48, 16];
let count = 0;

function linearSearch(array, item) {
  for (let i = 0; i < array.length; i++) {
    count += 1;
    if (array[i] === item) {
      return i;
    }
  }
  return null;
}

console.log(linearSearch(array, 1), count);

Двоичный (бинарный) поиск

Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

const array = [1, 2, 3, 4, 6, 7, 9, 11, 12, 13, 14, 15, 17, 19, 21, 25];
let count = 0;

function binarySearch(array, item) {
  let start = 0;
  let end = array.length;
  let middle;
  let found = false;
  let position = -1;

  if (item > array[end - 1]) return position;

  while (found === false && start <= end) {
    count += 1;

    middle = Math.floor((start + end) / 2);
     if (array[middle] === item) {
       found = true;
       position = middle;
       return position;
     }

     if (item < array[middle]) {
       end = middle - 1;
     } else {
       start = middle + 1; 
     }
  }

  return position;
}

Значение count показывает количество итераций

Бинарный поиск через рекурсию

function binarySearchRecursive(array, item, start, end) {
    let middle = Math.floor((start + end) / 2);

    if (item === array[middle]) {
      return middle;
    }

    if (item < array[middle]) {
      return binarySearchRecursive(array, item, start, middle - 1)
    } else {
      return binarySearchRecursive(array, item, middle + 1, end);
    }
}