Overview
Search algorithms are methods used to retrieve information stored within some data structure. The efficiency of a search depends heavily on how the data is organized.
Core Concepts
- Linear Search: Checks every element in sequence. Works on unsorted data. Time: $O(n)$.
- Binary Search: Repeatedly divides a sorted search interval in half. Works only on sorted data. Time: $O(\log n)$.
- Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Used for graphs/trees.
- Breadth-First Search (BFS): Explores all neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Used for finding the shortest path in unweighted graphs.
Code Examples
// Binary Search Implementation
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Use Cases
- Database Queries: Indexing uses B-Trees to perform binary-like searches on disk.
- AI Pathfinding: BFS and Dijkstra’s algorithm for finding shortest paths in games.
- File System Search: DFS for traversing directories to find a specific file.
Gotchas
- Forgetting to Sort: Applying Binary Search to an unsorted array will return incorrect results.
- Stack Overflow in DFS: Deeply nested graphs can cause recursion limits to be hit in DFS.