re:re:actable
Урок 013 минуты чтения

Что такое linear search и binary search?

На этой странице
Кратко

Linear search проверяет элементы по одному и работает за O(n). Binary search работает за O(log n), но требует отсортированного пространства поиска и на каждом шаге отбрасывает половину вариантов.

Вопрос

Чем linear search отличается от binary search и когда применим бинарный поиск?

function linearSearch(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i
  }
 
  return -1
}

Сложность:

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

Сложность:

Time: O(log n)
Space: O(1)

Binary search похож на поиск слова в бумажном словаре: открываем середину, смотрим, левее или правее нужное слово, и отбрасываем половину.

Пример: nums = [1, 3, 5, 7, 9, 11, 13], target = 11.

leftrightmidnums[mid]Действие
06377 < 11, ответ правее: left = 4
46511нашли, вернуть 5

Пример, когда элемента нет: target = 4.

leftrightmidnums[mid]Действие
06377 > 4, right = 2
02133 < 4, left = 2
22255 > 4, right = 1
21--left > right, диапазон пуст, вернуть -1

Почему mid + 1 и mid - 1, а не mid? Элемент nums[mid] мы уже проверили, его можно исключить. Если оставить left = mid, на двух элементах цикл может никогда не закончиться.

Запись left + Math.floor((right - left) / 2) дает то же, что Math.floor((left + right) / 2). В JS разницы нет, но в языках с 32-битными целыми left + right может переполниться, поэтому первую форму часто пишут по привычке.

Подробнее про границы - в уроке Как избегать off by one.

Binary search работает, когда можно отбросить половину поиска.

Обычно это:

  • отсортированный массив;
  • монотонная функция;
  • диапазон ответов;
  • задача "найти минимальное значение, при котором условие true".

Что отвечать на собеседовании?

Linear search подходит для неотсортированных данных и работает за O(n). Binary search требует отсортированного или монотонного пространства поиска и работает за O(log n), потому что на каждом шаге уменьшает область поиска вдвое.

Что важно помнить: частые ошибки

  • Использовать binary search на неотсортированном массиве.
  • Ошибаться в условии left <= right.
  • Делать mid = (left + right) / 2 без Math.floor.
  • Получать бесконечный цикл из-за неправильного обновления границ.
  • Не понимать binary search по answer space.

Мини-шпаргалка

  • Linear search - O(n).
  • Binary search - O(log n).
  • Binary требует порядок/монотонность.
  • left, right, mid.
  • Обновляй границы строго.
  • Возвращай -1 или agreed fallback.

Документация

Wikipedia: Binary search.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам