Implementing Search Algorithms in Python
Implement binary search, BFS, DFS, Dijkstra and A* in Python with correct data structures, edge-case handling and practical complexity guidance.
Choose the search algorithm from the data and the goal:
- Sorted sequence, exact value or boundary: binary search with
bisect. - Unweighted graph, fewest edges: breadth-first search (BFS).
- Reachability or exhaustive traversal: depth-first search (DFS).
- Weighted graph with non-negative edges: Dijkstra’s algorithm.
- Weighted pathfinding with a useful heuristic: A*.
The implementations below are complete Python programs. Each makes its preconditions explicit, handles duplicates or cycles, and shows the data structure that controls the frontier.
1. Binary search with Python’s bisect
Binary search requires a sequence sorted by the same ordering rule used by the search. Python’s bisect_left returns the first valid insertion position; bisect_right returns the position after equal values. Neither function proves that a target exists, so validate the index and compare the element yourself. The module uses the < relation while locating positions rather than calling equality for every step. See the Python bisect documentation.
from bisect import bisect_left, bisect_right
def index_of(sorted_values, target):
"""Return the first index equal to target, or -1 when absent."""
i = bisect_left(sorted_values, target)
if i != len(sorted_values) and sorted_values[i] == target:
return i
return -1
def equal_range(sorted_values, target):
"""Return the half-open range [start, end) containing target."""
start = bisect_left(sorted_values, target)
end = bisect_right(sorted_values, target)
return start, end
values = [1, 2, 2, 2, 5, 9]
print(index_of(values, 2)) # 1
print(index_of(values, 7)) # -1
print(equal_range(values, 2)) # (1, 4)
Insertion and maintenance costs
insort performs an O(log n) search for the insertion point, then shifts elements in a Python list. The list insertion is O(n), so repeated ordered-list insertion is not an O(log n) operation. A dictionary or set is usually a better choice for direct membership lookup; Python’s documentation specifically notes that dictionaries are more performant for locating specific values. Bisect operations are also not thread-safe when another thread concurrently mutates or bisects the same sequence.
2. Breadth-first search (BFS)
BFS explores a graph level by level. In an unweighted graph, the first time a node is discovered gives a shortest path measured in edges. Use collections.deque as a FIFO queue: remove with popleft() and append newly discovered nodes. Mark a node when enqueuing it, which prevents cycles and duplicate work.
from collections import deque
def bfs_shortest_path(graph, start, goal):
"""Return a shortest unweighted path, or None if goal is unreachable."""
queue = deque([start])
parent = {start: None}
while queue:
node = queue.popleft()
if node == goal:
path = []
while node is not None:
path.append(node)
node = parent[node]
return path[::-1]
for neighbor in graph.get(node, ()):
if neighbor not in parent:
parent[neighbor] = node
queue.append(neighbor)
return None
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["D", "E"],
"D": ["F"],
"E": ["F"],
"F": [],
}
print(bfs_shortest_path(graph, "A", "F")) # ['A', 'B', 'D', 'F']
With adjacency lists, BFS runs in O(V + E) time and uses O(V) memory for the queue and discovered set, where V is the number of vertices and E the number of edges. The exact constants depend on your graph representation.
3. Depth-first search (DFS)
DFS follows one branch as far as possible before backtracking. It is useful for reachability, connected components, cycle checks and topological-style traversals. It does not guarantee a shortest path.
def dfs_reachable(graph, start, goal):
stack = [start]
visited = set()
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
if node == goal:
return True
stack.extend(reversed(graph.get(node, ())))
return False
def dfs_order(graph, start):
"""Return preorder traversal without revisiting cyclic nodes."""
stack = [start]
visited = set()
order = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
stack.extend(reversed(graph.get(node, ())))
return order
An explicit stack avoids Python’s recursion-depth limit. Recursive DFS can be clearer for small trees, but increase neither the recursion limit nor trust it for attacker-controlled depth without considering stack exhaustion.
4. Dijkstra’s algorithm with heapq
Dijkstra computes minimum weighted distances when every edge weight is non-negative. Store tentative distances in a min-heap and discard stale entries when a shorter route has already been found. The heapq documentation defines a min-heap whose smallest item is at index zero; heapify transforms a list in linear time.
import heapq
from itertools import count
def dijkstra(graph, start):
distances = {start: 0}
previous = {start: None}
serial = count() # tie-breaker for equal priorities
heap = [(0, next(serial), start)]
while heap:
distance, _, node = heapq.heappop(heap)
if distance != distances.get(node):
continue # stale heap entry
for neighbor, weight in graph.get(node, ()):
if weight < 0:
raise ValueError("Dijkstra requires non-negative edge weights")
candidate = distance + weight
if candidate < distances.get(neighbor, float("inf")):
distances[neighbor] = candidate
previous[neighbor] = node
heapq.heappush(heap, (candidate, next(serial), neighbor))
return distances, previous
def restore_path(previous, target):
if target not in previous:
return None
path = []
while target is not None:
path.append(target)
target = previous[target]
return path[::-1]
weighted = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
distances, previous = dijkstra(weighted, "A")
print(distances["D"]) # 4
print(restore_path(previous, "D")) # ['A', 'C', 'B', 'D']
The counter in each heap entry makes equal priorities comparable even when node objects cannot be ordered. With a binary heap and adjacency lists, the usual bound is O((V + E) log V), assuming the stated representation and non-negative weights.
5. A* search
A* adds a heuristic h(node) to the cost already traveled g(node). For guaranteed optimal paths, the heuristic must not overestimate the remaining cost; consistency also lets implementations avoid reopening many nodes. If the heuristic is zero, A* behaves like Dijkstra.
import heapq
from itertools import count
def a_star(graph, start, goal, heuristic):
serial = count()
g_score = {start: 0}
parent = {start: None}
heap = [(heuristic(start), next(serial), start)]
while heap:
_, _, node = heapq.heappop(heap)
if node == goal:
return restore_path(parent, goal), g_score[node]
for neighbor, weight in graph.get(node, ()):
tentative = g_score[node] + weight
if tentative < g_score.get(neighbor, float("inf")):
g_score[neighbor] = tentative
parent[neighbor] = node
priority = tentative + heuristic(neighbor)
heapq.heappush(heap, (priority, next(serial), neighbor))
return None, float("inf")
For a grid, a Manhattan-distance heuristic is appropriate when movement is four-directional and each step has the same cost. Do not use that heuristic unchanged for diagonal movement or variable terrain costs.
6. Choosing the right implementation
| Goal | Precondition | Frontier | Typical choice |
|---|---|---|---|
| Exact value in ordered data | Sorted sequence | Indices | bisect_left plus equality check |
| Range boundaries | Sorted sequence | Indices | bisect_left/bisect_right |
| Fewest edges | Unweighted graph | FIFO deque | BFS |
| Reachability or full traversal | Any graph | LIFO stack | DFS |
| Lowest weighted cost | Non-negative weights | Min-heap | Dijkstra |
| Lowest cost with domain knowledge | Valid heuristic | Min-heap | A* |
7. Testing and edge cases
- Test an empty sequence, a one-element sequence, an absent target and duplicate targets.
- For graphs, test a missing start node, an unreachable goal, self-loops and cycles.
- For weighted searches, test zero-weight edges and reject negative weights for Dijkstra.
- Use immutable, comparable heap keys or include a unique counter as a tie-breaker.
- Define whether endpoints are inclusive or exclusive before implementing range searches.
- Keep the visited/discovered set separate from path reconstruction data when multiple paths exist.
8. Troubleshooting
| Symptom | Likely cause | Fix |
|---|---|---|
| Binary search returns an index for a missing value | Insertion position was mistaken for a match | Check i < len(values) and equality. |
| BFS or DFS never finishes | Cycles are revisited | Mark nodes when discovered or popped. |
| Shortest path is wrong | BFS used on weighted edges, or negative weights passed to Dijkstra | Use Dijkstra/A* for non-negative weights and validate weights. |
TypeError from heapq |
Equal priorities force comparison of payload objects | Add a monotonically increasing counter. |
Recursive DFS raises RecursionError |
Graph depth exceeds Python’s recursion limit | Use an explicit stack. |
| Results change between runs | Neighbor iteration order is unstable | Use a deterministic adjacency order when reproducibility matters. |
9. Performance, reliability and cost
Measure preprocessing as well as each query. A sorted list supports fast boundary lookup but costly insertions; a dictionary or set trades ordering for fast average membership. For graph searches, memory often becomes the limiting resource before CPU: BFS can hold an entire frontier, while DFS can follow a deep branch. Heap entries may become stale after a better distance is found, so discard them as shown. For production workloads, define cancellation, maximum nodes, timeouts and input-size limits around the algorithm.
10. Or skip the browser setup: capture algorithm output with ScreenshotNeo
If you are publishing search visualizations or documentation pages, ScreenshotNeo can capture the rendered result through one request. Cookie banners, newsletter popups and chat widgets are removed before the shot. Bot checks, blank pages and failed loads are not billed, and the response reports the page verdict and billing status in headers. An MCP server provides take_screenshot, get_page_info and capture_pdf tools for Claude, Cursor and other MCP clients. The free plan includes 1,000 screenshots per month with no card; paid plans start at $5 for 3,000 shots.
See the ScreenshotNeo API documentation for all options, including full-page capture, element selectors, custom CSS, waits, blocking rules, headers, cookies, device presets, PDFs, caching, signed links and bulk capture.
cURL
curl -G "https://api.screenshotneo.com/v1/shot" -d access_key=YOUR_API_KEY --data-urlencode url=https://stripe.com -o shot.webpPython
import requests
r = requests.get("https://api.screenshotneo.com/v1/shot", params={"access_key": "YOUR_API_KEY", "url": "https://stripe.com"}, timeout=90)
open("shot.webp", "wb").write(r.content)Node.js
const q = new URLSearchParams({ access_key: 'YOUR_API_KEY', url: 'https://stripe.com' });
const res = await fetch(`https://api.screenshotneo.com/v1/shot?${q}`);Create a free ScreenshotNeo account with 1,000 screenshots each month and no card.
11. FAQ
Is bisect faster than a dictionary?
For exact membership, dictionaries are generally the better structure. Bisect is valuable when you need ordered boundaries or ranges.
Should I mark BFS nodes visited on enqueue or dequeue?
Marking on enqueue prevents the same node entering the queue multiple times. It also preserves the first discovered shortest parent in an unweighted graph.
Can Dijkstra handle negative edges?
No. Use an algorithm designed for negative weights, such as Bellman–Ford, or change the model.
When is A* preferable to Dijkstra?
When you have a cheap heuristic that estimates remaining cost accurately enough to reduce exploration while preserving the required optimality conditions.
