Searching and traversal

Linear search works anywhere but scans every candidate. Binary search is faster only when the search space is sorted or monotonic. BFS explores by distance in unweighted graphs; DFS explores depth and is useful for components, backtracking, and recursive tree processing.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: The key signal is proving the precondition: sorted array, monotonic predicate, unweighted graph, or a visited set for cyclic structures.

Common pitfalls: Binary search off-by-one errors are common. BFS with Array.shift can be inefficient in JavaScript. Recursive DFS can overflow on deep inputs.

Checklist:

• Prove monotonicity.
• Define inclusive or exclusive bounds.
• Use a queue head index.
• Track visited nodes.