PrepBro
← Назад к вопросам

Бинарный поиск в отсортированном массиве

1.6 Junior🔥 201 комментариев
#Node.js и JavaScript#Алгоритмы и структуры данных

Условие

Напишите функцию binarySearch(arr, target), которая находит индекс элемента в отсортированном массиве. Если элемент не найден, верните -1:

function binarySearch(arr, target) {
  // Ваш код
}

const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(arr, 7));  // 3
console.log(binarySearch(arr, 1));  // 0
console.log(binarySearch(arr, 15)); // 7
console.log(binarySearch(arr, 6));  // -1

Что проверяется

  • Алгоритм бинарного поиска
  • Понимание сложности O(log n)
  • Работа с указателями (left, right, mid)

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение: Бинарный поиск

Итеративная реализация

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const midValue = arr[mid];
    
    if (midValue === target) {
      return mid;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}

const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(arr, 7));  // 3
console.log(binarySearch(arr, 1));  // 0
console.log(binarySearch(arr, 15)); // 7
console.log(binarySearch(arr, 6));  // -1

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

function binarySearchRecursive(arr: number[], target: number): number {
  return helper(arr, target, 0, arr.length - 1);
}

function helper(
  arr: number[],
  target: number,
  left: number,
  right: number
): number {
  if (left > right) return -1;
  
  const mid = left + Math.floor((right - left) / 2);
  
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    return helper(arr, target, mid + 1, right);
  } else {
    return helper(arr, target, left, mid - 1);
  }
}

Как работает

Поиск 7 в [1, 3, 5, 7, 9, 11, 13, 15]

Шаг 1: left=0, right=7, mid=3
       arr[3]=7 === 7? ДА → return 3 ✓

Поиск 6 (не существует):
Шаг 1: left=0, right=7, mid=3
       arr[3]=7 > 6 → right=2
Шаг 2: left=0, right=2, mid=1
       arr[1]=3 < 6 → left=2
Шаг 3: left=2, right=2, mid=2
       arr[2]=5 < 6 → left=3
Шаг 4: left=3, right=2 (left > right) → return -1

Сложность

  • Время: O(log n) — пространство поиска сокращается вдвое на каждом шаге
  • Память: O(1) итеративно, O(log n) рекурсивно
  • На массиве из 1M элементов максимум 20 итераций

Важно: Избегаем overflow

// ❌ Неправильно
const mid = Math.floor((left + right) / 2); // может быть overflow

// ✅ Правильно
const mid = left + Math.floor((right - left) / 2);

Варианты: Поиск границ

// Первое вхождение элемента
function findFirst(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1, result = -1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) {
      result = mid;
      right = mid - 1; // Ищем слева
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

// Последнее вхождение элемента
function findLast(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1, result = -1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) {
      result = mid;
      left = mid + 1; // Ищем справа
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

// Позиция для вставки
function searchInsert(arr: number[], target: number): number {
  let left = 0, right = arr.length;
  
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}

Edge cases

binarySearch([], 5);              // -1 (пустой)
binarySearch([5], 5);             // 0 (один элемент)
binarySearch([-10, 0, 10], 0);    // 1 (отрицательные)
binarySearch([5, 5, 5, 5], 5);    // 0, 1, 2 или 3 (дубликаты)

Производительность (на 1M элементов)

  • indexOf (линейный): ~5ms
  • binarySearch: <1ms ✓

Тесты

test('binarySearch base', () => {
  const arr = [1, 3, 5, 7, 9];
  expect(binarySearch(arr, 5)).toBe(2);
  expect(binarySearch(arr, 6)).toBe(-1);
  expect(binarySearch(arr, 1)).toBe(0);
  expect(binarySearch(arr, 9)).toBe(4);
});
Бинарный поиск в отсортированном массиве | PrepBro