Реализовать бинарный поиск

Решение

Задача на бинарный поиск — классическая для показа понимания алгоритмов и оптимизации.

Решение 1: Итеративный бинарный поиск

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];

    if (midValue === target) {
      return mid;
    } else if (midValue < target) {
      left = mid + 1;  // Ищем справа
    } else {
      right = mid - 1; // Ищем слева
    }
  }

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

// Тесты
console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5], 1));              // 0
console.log(binarySearch([1, 2, 3, 4, 5], 5));              // 4
console.log(binarySearch([1, 2, 3, 4, 5], 6));              // -1
console.log(binarySearch([], 1));                           // -1

Анализ:

• Временная сложность: O(log n)
• Пространственная сложность: O(1)
• Эффективна для больших отсортированных массивов

Решение 2: Рекурсивный бинарный поиск

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1; // Не найдено
  }

  const mid = Math.floor((left + right) / 2);
  const midValue = arr[mid];

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

// Тесты
console.log(binarySearchRecursive([1, 2, 3, 4, 5, 6, 7, 8, 9], 5)); // 4
console.log(binarySearchRecursive([1, 2, 3, 4, 5], 1));              // 0
console.log(binarySearchRecursive([1, 2, 3, 4, 5], 5));              // 4
console.log(binarySearchRecursive([1, 2, 3, 4, 5], 6));              // -1
console.log(binarySearchRecursive([], 1));                           // -1

Анализ:

• Временная сложность: O(log n)
• Пространственная сложность: O(log n) - стек вызовов
• Рекурсия может быть понятнее для некоторых

Решение 3: С TypeScript типизацией

function binarySearch<T>(arr: T[], target: T, compareFn?: (a: T, b: T) => number): number {
  let left = 0;
  let right = arr.length - 1;

  const compare = compareFn || ((a: any, b: any) => a - b);

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const cmp = compare(arr[mid], target);

    if (cmp === 0) {
      return mid;
    } else if (cmp < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

// Использование с числами
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2

// Использование с объектами
const users = [
  { id: 1, name: "Alice" },
  { id: 3, name: "Bob" },
  { id: 5, name: "Charlie" }
];

const idx = binarySearch(
  users,
  { id: 3, name: "" },
  (a, b) => a.id - b.id
);
console.log(idx); // 1

Решение 4: Найти позицию вставки (для несортированных элементов)

function binarySearchInsertPosition(arr, target) {
  let left = 0;
  let right = arr.length;

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

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

  return left; // Позиция для вставки
}

// Использование
console.log(binarySearchInsertPosition([1, 3, 5, 7], 4)); // 2
console.log(binarySearchInsertPosition([1, 3, 5, 7], 0)); // 0
console.log(binarySearchInsertPosition([1, 3, 5, 7], 8)); // 4

Решение 5: Практическое применение

// Найти первый элемент >= target
function lowerBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}

// Найти первый элемент > target
function upperBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}

// Использование
const arr = [1, 2, 2, 2, 3, 4, 5];
console.log(lowerBound(arr, 2)); // 1 - первое 2
console.log(upperBound(arr, 2)); // 4 - первый элемент > 2

Сравнение подходов

Визуальная демонстрация

Массив: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Ищем: 5

Шаг 1: left=0, right=8, mid=4, arr[4]=5 ✓ Найдено!
Возврат: 4

Если ищем 2:
Шаг 1: left=0, right=8, mid=4, arr[4]=5 > 2, right=3
Шаг 2: left=0, right=3, mid=1, arr[1]=2 ✓ Найдено!
Возврат: 1

Если ищем 10:
Шаг 1: left=0, right=8, mid=4, arr[4]=5 < 10, left=5
Шаг 2: left=5, right=8, mid=6, arr[6]=7 < 10, left=7
Шаг 3: left=7, right=8, mid=7, arr[7]=8 < 10, left=8
Шаг 4: left=8, right=8, mid=8, arr[8]=9 < 10, left=9
Шаг 5: left=9, right=8, left > right, завершить
Возврат: -1

Best Practices

1. Проверить, отсортирован ли массив перед использованием
2. Использовать Math.floor() для целых индексов
3. Избегать переполнения при вычислении mid (left + (right - left) / 2)
4. Обрабатывать граничные случаи - пустой массив, один элемент
5. Итеративный вариант предпочтительнее - меньше памяти

Рекомендации для собеседования

1. Начните с итеративного варианта
2. Объясните логику left/right и mid
3. Покажите рекурсивный вариант
4. Обсудите временную сложность O(log n)
5. Упомяните lower/upper bound варианты

Итог: Итеративный бинарный поиск - стандартное, эффективное решение.