Searching Algorithms Cheat Sheet
Covers linear and binary search, graph traversal with BFS and DFS, and guidance on choosing the right search strategy.
1 PageIntermediateApr 15, 2026
Search Strategies
Common approaches to finding data, ordered by typical use case.
- Linear Search- O(n) time, O(1) space; checks each element sequentially, works on unsorted data
- Binary Search- O(log n) time, O(1) space; requires sorted data, repeatedly halves the search range
- Breadth-First Search (BFS)- O(V + E) time; explores a graph level by level using a queue, finds shortest paths in unweighted graphs
- Depth-First Search (DFS)- O(V + E) time; explores as far as possible along each branch using a stack or recursion
- Hash-based Lookup- Average O(1) time via a hash table or set; no ordering requirement but uses extra memory
Linear vs Binary Search
Two fundamental search algorithms compared.
python
# Linear search: O(n)def linear_search(arr, target): for i, val in enumerate(arr): if val == target: return i return -1# Binary search: O(log n), requires sorted inputdef binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1import bisectbisect.bisect_left([1, 3, 5, 7], 5) # => 2, built-in binary search
BFS & DFS Graph Search
Traversing a graph represented as an adjacency list.
python
from collections import dequedef bfs(graph, start): visited = {start} queue = deque([start]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return orderdef dfs(graph, start, visited=None, order=None): if visited is None: visited, order = set(), [] visited.add(start) order.append(start) for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited, order) return order
Choosing a Strategy
Matching the search algorithm to the problem.
- Unsorted, small data- Linear search; the overhead of sorting first isn't worth it for one-off lookups
- Sorted data, many queries- Binary search or a sorted structure amortizes the O(n log n) sort cost across queries
- Shortest path, unweighted graph- BFS guarantees the fewest edges to reach a target
- Exploring all paths- DFS is simpler to implement recursively and uses less memory than BFS for deep graphs
- Frequent exact-match lookups- A hash set or map beats both linear and binary search with O(1) average time
Binary Search on the Answer Space
Applying binary search to a monotonic predicate over possible answers instead of an array index.
python
# Find the minimum capacity to ship all packages within `days` daysdef can_ship(weights, capacity, days): needed, current = 1, 0 for w in weights: if current + w > capacity: needed += 1 current = 0 current += w return needed <= daysdef min_capacity(weights, days): lo, hi = max(weights), sum(weights) while lo < hi: mid = lo + (hi - lo) // 2 if can_ship(weights, mid, days): hi = mid # mid works, try smaller else: lo = mid + 1 # mid too small, need more capacity return lomin_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) # => 15
Search in a Rotated Sorted Array
Binary search variant that works even after the sorted array has been rotated at an unknown pivot.
python
def search_rotated(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # left half is sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half is sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1search_rotated([4, 5, 6, 7, 0, 1, 2], 0) # => 4
Exponential & Jump Search
Sub-linear strategies for unbounded or block-structured sorted sequences.
python
import math# Exponential search: probe 1, 2, 4, 8... to bracket target, then binary searchdef exponential_search(arr, target): if arr[0] == target: return 0 n = len(arr) bound = 1 while bound < n and arr[bound] < target: bound *= 2 lo, hi = bound // 2, min(bound, n - 1) while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1# Jump search: skip sqrt(n) at a time, then linear scan the blockdef jump_search(arr, target): n = len(arr) step = int(math.sqrt(n)) prev = 0 curr = step while curr < n and arr[curr - 1] < target: prev, curr = curr, curr + step for i in range(prev, min(curr, n)): if arr[i] == target: return i return -1
Advanced Search Techniques
Specialized search strategies beyond plain binary/linear search.
- Ternary Search- O(log3 n); finds the extremum of a unimodal function by comparing two interior points each iteration
- Interpolation Search- O(log log n) average on uniformly distributed sorted data; estimates position via value proportion instead of always halving
- KMP (Knuth-Morris-Pratt)- O(n + m) substring search; precomputes a failure function to avoid re-scanning matched characters
- Rabin-Karp- O(n + m) average via rolling hash; efficient for multi-pattern search since hashes are cheap to compare
- A* Search- Informed graph search combining path cost with a heuristic estimate; optimal when the heuristic is admissible
- Fractional Cascading- Amortizes repeated binary searches across multiple sorted lists down to O(log n + k) total instead of O(k log n)
- Van Emde Boas Tree- O(log log U) search/insert/predecessor over a bounded integer universe U, at the cost of extra memory
KMP Substring Search
Linear-time exact string matching using a precomputed longest-prefix-suffix (LPS) table.
python
def build_lps(pattern): lps = [0] * len(pattern) length = 0 i = 1 while i < len(pattern): if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 elif length: length = lps[length - 1] else: lps[i] = 0 i += 1 return lpsdef kmp_search(text, pattern): lps = build_lps(pattern) matches, i, j = [], 0, 0 while i < len(text): if text[i] == pattern[j]: i += 1 j += 1 if j == len(pattern): matches.append(i - j) j = lps[j - 1] elif j: j = lps[j - 1] else: i += 1 return matcheskmp_search("ababcabcabababd", "abab") # => [0, 8, 10]
Pro Tip
Binary search bugs almost always come from the loop bounds or midpoint update — use lo <= hi with lo = mid + 1 / hi = mid - 1, and prefer mid = lo + (hi - lo) // 2 to avoid overflow in fixed-width integer languages.
Was this cheat sheet helpful?
Explore Topics
#SearchingAlgorithms#SearchingAlgorithmsCheatSheet#Programming#Intermediate#SearchStrategies#LinearVsBinarySearch#BFS#DFS#DataStructures#Algorithms#CheatSheet#SkillVeris
