Есть ли требования к массиву передаваемому на вход в функцию бинарного поиска?

Требования к массиву для бинарного поиска

Основной этап

Бинарный поиск — это алгоритм, который работает только с отсортированными массивами. Если массив не отсортирован, алгоритм работать не будет, и ты получишь неправильный результат.

Главное требование: СОРТИРОВКА

Массив ОБЯЗАТЕЛЬНО должен быть отсортирован в порядке возрастания (или по определённому критерию, если ты используешь компаратор).

// Правильно — массив отсортирован
const sortedArray = [1, 3, 5, 7, 9, 11, 15];
binarySearch(sortedArray, 7); // Найдёт 7

// Неправильно — массив не отсортирован
const unsortedArray = [5, 1, 9, 3, 7];
binarySearch(unsortedArray, 7); // Может вернуть неправильный результат

Реализация бинарного поиска

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) {
      return mid; // Найдено
    } else if (arr[mid] < target) {
      left = mid + 1; // Ищем в правой половине
    } else {
      right = mid - 1; // Ищем в левой половине
    }
  }

  return -1; // Не найдено
}

console.log(binarySearch([1, 3, 5, 7, 9], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9], 4)); // -1

Дополнительные требования

1. Сравниваемые элементы должны быть сравнимыми

Массив должен содержать элементы, которые можно сравнить между собой (числа, строки).

// Числа
binarySearch([1, 2, 3, 4, 5], 3);

// Строки (лексикографический порядок)
binarySearch(['apple', 'banana', 'cherry'], 'banana');

2. Для объектов нужен компаратор

function binarySearchObjects(arr, target, compareFn) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const cmp = compareFn(arr[mid], target);
    
    if (cmp === 0) {
      return mid;
    } else if (cmp < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

const users = [
  {id: 1, name: 'Alice'},
  {id: 3, name: 'Bob'},
  {id: 5, name: 'Charlie'}
];

const compare = (obj, target) => obj.id - target.id;
const result = binarySearchObjects(users, {id: 3}, compare);
console.log(result); // 1

Временная и пространственная сложность

• Временная сложность: O(log n) — намного быстрее линейного поиска O(n)
• Пространственная сложность: O(1) для итеративной версии, O(log n) для рекурсивной

Сравнение с линейным поиском

// Линейный поиск — O(n)
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

На массиве из 1,000,000 элементов:

• Линейный поиск: в среднем 500,000 итераций
• Бинарный поиск: максимум 20 итераций

Рекурсивная реализация

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1;
  }

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

Практическое применение

Бинарный поиск используется в:

• Поиске элемента в большом отсортированном массиве
• Поиске на диапазонах (левая/правая граница)
• Базе данных с индексами
• Версионировании программного обеспечения

Ключевой момент: если массив не отсортирован, не используй бинарный поиск. Сначала отсорти массив, либо используй линейный поиск.