Introduction

Search algorithms answer two different kinds of questions: "is this target in my data" and "how do I reach a goal state in a search space." The complexity depends not only on the algorithm but also on the data structure and problem model. That is why O(log n) binary search is excellent on sorted arrays yet useless on arbitrary graphs, while graph search algorithms solve pathfinding problems that array search cannot even express.

Start with the Simplest Data Search

Linear search checks each element until it finds the target or reaches the end.

1def linear_search(items, target):
2    for index, value in enumerate(items):
3        if value == target:
4            return index
5    return -1
6
7print(linear_search([4, 7, 9, 12], 9))

Its complexity is:

1. Best case: O(1) if the first element matches.
2. Worst case: O(n) if the element is absent or last.

Linear search works on unsorted data and is often the right answer for short lists where setup costs matter more than asymptotic analysis.

Use Binary Search Only on Sorted Data

Binary search repeatedly halves the search space, which is why it is much faster on large sorted collections.

1def binary_search(items, target):
2    left, right = 0, len(items) - 1
3
4    while left <= right:
5        mid = (left + right) // 2
6        if items[mid] == target:
7            return mid
8        if items[mid] < target:
9            left = mid + 1
10        else:
11            right = mid - 1
12
13    return -1
14
15print(binary_search([1, 3, 5, 7, 9, 11], 7))

Binary search has O(log n) worst-case time, but only if the data is sorted and random access is cheap. Using it on unsorted input breaks correctness, not just performance.

Search Graphs with BFS or DFS

Once the problem is a graph or tree rather than a flat array, the search question changes. Breadth-first search explores layer by layer and is useful for shortest paths in unweighted graphs. Depth-first search goes deep along one branch before backtracking.

Breadth-first search example:

1from collections import deque
2
3def bfs(graph, start, goal):
4    queue = deque([start])
5    visited = {start}
6
7    while queue:
8        node = queue.popleft()
9        if node == goal:
10            return True
11
12        for neighbor in graph[node]:
13            if neighbor not in visited:
14                visited.add(neighbor)
15                queue.append(neighbor)
16
17    return False
18
19graph = {
20    "A": ["B", "C"],
21    "B": ["D"],
22    "C": [],
23    "D": []
24}
25
26print(bfs(graph, "A", "D"))

For a graph with V vertices and E edges, both BFS and DFS run in O(V + E) time when implemented with adjacency lists.

Use Heuristics When Search Spaces Are Large

Some search problems are too large for blind exploration. A* search uses a heuristic estimate to guide exploration toward the goal.

Conceptually, A* prioritizes nodes by:

1. Cost so far.
2. Estimated remaining cost.

That makes it powerful for pathfinding, but the performance depends heavily on the heuristic quality. A poor heuristic reduces A* toward more expensive uninformed search behavior.

Even when the asymptotic worst case is still large, a good heuristic can make a practical difference of orders of magnitude.

Complexity Depends on the Representation

The phrase "search algorithm complexity" is incomplete unless you also state the data assumptions. Consider the difference:

1. Array membership in unsorted data: linear search, O(n).
2. Array membership in sorted data: binary search, O(log n).
3. Hash table lookup: expected O(1).
4. Graph reachability: BFS or DFS, O(V + E).

The fastest search method often comes from choosing the right data structure before you even choose the algorithm.

Measure Space Complexity Too

Time complexity gets the attention, but memory matters too. DFS can use less memory than BFS on wide graphs because BFS stores an entire frontier. Binary search uses little extra space in its iterative form, while some recursive versions consume call stack depth. In real systems, memory pressure can make an algorithm with similar time complexity the better practical choice.

Pick the Algorithm That Matches the Question

Ask what the actual search problem is:

1. Find a value in a small unsorted list: linear search is often fine.
2. Search a sorted collection: binary search is the right baseline.
3. Explore reachability or shortest paths in an unweighted graph: BFS.
4. Traverse all paths or use backtracking: DFS.
5. Goal-directed pathfinding with a good heuristic: A*.

Most search mistakes happen when an algorithm is chosen by name recognition rather than by problem shape.

Common Pitfalls

• Applying binary search to data that is not sorted.
• Discussing search complexity without mentioning the data structure assumptions.
• Using BFS where memory is too constrained for the frontier size.
• Assuming an asymptotically faster algorithm is always better for tiny inputs.
• Treating heuristic search as universally superior when the heuristic quality may be poor.

Summary

• Search algorithms solve different problems depending on whether the data is a list, tree, graph, or weighted search space.
• Linear search is simple and flexible but costs O(n) in the worst case.
• Binary search is O(log n) but requires sorted, indexable data.
• BFS and DFS are fundamental graph-search tools with O(V + E) time on adjacency lists.
• Complexity analysis only makes sense when paired with the right data assumptions and practical constraints.