Алгоритмы поиска

Какие есть алгоритмы поиска?

• Линейный поиск (Linear Search)
• Двоичный поиск (Binary Search)
• Интерполяционный поиск (Interpolation Search)
• Поиск по хэш-таблице (Hash Table Search) ... и так далее

Двоичный поиск (Binary Search)

const binary = () => {
  function binarySearch(arr, target) {
    // Инициализация левой границы поиска
    let left = 0;
    // Инициализация правой границы поиска
    let right = arr.length - 1;

    // Цикл, который выполняется пока левая граница не станет больше правой
    while (left <= right) {
      // Вычисление середины массива
      const mid = Math.floor((left + right) / 2);
      // Получение значения в середине массива
      const midValue = arr[mid];
      console.log(midValue);

      // Проверка, равно ли серединное значение искомому
      if (midValue === target) {
        return mid; // Возвращение индекса найденного элемента
      } else if (midValue < target) {
        left = mid + 1; // Сдвиг левой границы за середину, исключая текущую середину
      } else {
        right = mid - 1; // Сдвиг правой границы до середины, исключая текущую середину
      }
    }

    return -1; // Возвращение -1, если элемент не найден
  } // Сложность log по основанию 2 от n + 1 -> O(log n)

  // Пример использования функции двоичного поиска
  const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; // Отсортированный массив
  const target = 7; // Значение, которое нужно найти
  const index = binarySearch(sortedArray, target); // Вызов функции и сохранение результата

  // Проверка, найден ли элемент и вывод соответствующего сообщения
  if (index !== -1) {
    console.log(`Элемент найден на позиции: ${index}`);
  } else {
    console.log("Элемент не найден.");
  }
};
// binary();