Всегда ли бинарный поиск работает с индексами?

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

Ключевые условия для бинарного поиска:

1. Данные должны быть отсортированы (по возрастанию или убыванию).
2. Должен существовать механизм прямого доступа к элементам по индексу (как в массиве).

Пример реализации на JavaScript/Node.js:

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

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midValue = sortedArray[mid];

        if (midValue === target) {
            return mid; // Элемент найден
        }
        if (midValue < target) {
            left = mid + 1; // Ищем в правой половине
        } else {
            right = mid - 1; // Ищем в левой половине
        }
    }
    return -1; // Элемент не найден
}

// Использование
const arr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(arr, 7)); // 3
console.log(binarySearch(arr, 4)); // -1

Сложность: O(log n), что делает его эффективным для больших отсортированных массивов. Если данные не отсортированы, предварительная сортировка за O(n log n) может свести на нет преимущество бинарного поиска.