Поиск и обход

Linear search работает везде, но сканирует каждый candidate. Binary search быстрее только когда search space sorted или monotonic. BFS исследует по distance в unweighted graphs; DFS идет в глубину и полезен для components, backtracking и recursive tree processing.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Ключевой сигнал - доказать precondition: sorted array, monotonic predicate, unweighted graph или visited set для cyclic structures.

Типовые ошибки: Off-by-one ошибки в binary search очень часты. BFS с Array.shift может быть inefficient в JavaScript. Recursive DFS может переполнить stack на deep inputs.

Чеклист:

• Докажите monotonicity.
• Определите inclusive или exclusive bounds.
• Используйте head index для queue.
• Отслеживайте visited nodes.