Search Algorithms
Learn how to efficiently find elements in data structures using Binary Search, Depth-First Search (DFS), and Breadth-First Search (BFS).
Binary Search
Binary Search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half.
How It Works
- Find the middle element of the array
- If target equals middle, return position
- If target is less than middle, search left half
- If target is greater than middle, search right half
- Repeat until found or array is exhausted
JavaScript Implementation
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // Found!
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Not found
}
Time Complexity
O(log n)
Space Complexity
O(1)
Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of nodes to visit.
DFS Implementation
// Recursive DFS for a graph
function dfs(graph, node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
console.log(node); // Process node
for (const neighbor of graph[node]) {
dfs(graph, neighbor, visited);
}
}
// Iterative DFS using stack
function dfsIterative(graph, start) {
const stack = [start];
const visited = new Set();
while (stack.length > 0) {
const node = stack.pop();
if (visited.has(node)) continue;
visited.add(node);
console.log(node);
for (const neighbor of graph[node]) {
stack.push(neighbor);
}
}
}Use Cases for DFS
- Finding paths in a maze
- Detecting cycles in a graph
- Topological sorting
- Solving puzzles (Sudoku, N-Queens)
Breadth-First Search (BFS)
BFS explores all neighbors at the present depth before moving to nodes at the next depth level. It uses a queue data structure.
BFS Implementation
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
while (queue.length > 0) {
const node = queue.shift();
console.log(node); // Process node
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}Use Cases for BFS
- Finding shortest path in unweighted graphs
- Level-order tree traversal
- Finding connected components
- Social network connections
DFS vs BFS Comparison
| Aspect | DFS | BFS |
|---|---|---|
| Data Structure | Stack | Queue |
| Exploration | Goes deep first | Goes wide first |
| Shortest Path | No guarantee | Yes (unweighted) |
| Memory Usage | O(h) - height | O(w) - width |