Searching Algorithms

Introduction to Searching

Searching is one of the most fundamental operations in computer science. Whether you're looking up a contact in your phone, finding a file on your computer, or querying a database, searching algorithms are at work. Understanding different searching techniques and when to use them is crucial for writing efficient code.

This chapter covers the two fundamental searching algorithms for arrays and lists — Linear Search and Binary Search — plus hash tables, which sidestep searching entirely and are what most real lookup code actually uses. For graph traversal and pathfinding (DFS, BFS, Dijkstra's, Bellman-Ford, Floyd-Warshall, A*), see Graph Algorithms. For tree-based search, see Binary Search Trees.

Prerequisites: Before studying Binary Search, you should understand sorting algorithms (see Sorting Algorithms), as Binary Search requires sorted data.

Searching Algorithms

Algorithm Comparison

Here's a comparison of the two fundamental searching algorithms for arrays and lists:

Hash Tables: The O(1) Option

Linear and binary search both scan or bisect a collection. A hash table avoids searching altogether: it computes the location of a key directly from the key itself. This is the most-used lookup structure in practice — Python's dict and set, Java's HashMap, and JavaScript objects are all hash tables — and it is worth understanding before either algorithm above.

# Python's dict IS a hash table
seen = {}
seen["apple"] = 3          # hash("apple") -> bucket index -> store there
value = seen["apple"]      # same computation, go straight to the bucket

# The classic use: turn a nested O(n^2) scan into a single O(n) pass
def two_sum(nums, target):
    seen = {}                              # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:             # O(1) average, not O(n)
            return [seen[target - x], i]
        seen[x] = i
    return []

Collisions

Two different keys can hash to the same bucket. Every hash table needs a strategy for that:

• Separate chaining: each bucket holds a list (or, above a threshold, a tree) of entries. Simple, and degrades gracefully as the table fills.
• Open addressing: on a collision, probe for another free slot — linearly, quadratically, or by double hashing. Better cache behaviour since everything lives in one array, but performance falls off sharply as the load factor approaches 1, and deletion needs tombstones.

Complexity

The O(1) is an average, not a guarantee. If every key collides, every operation degrades to a linear scan of one bucket. This is not merely theoretical: hash flooding is a real denial-of-service attack in which a client sends keys deliberately chosen to collide, turning an O(n) request handler into an O(n²) one. It hit PHP, Java, Python and Ruby web frameworks in 2011. The defence is hash randomization — seeding the hash function with a per-process random value, which Python has enabled by default since 3.3.

"Amortized" for insert reflects resizing: when the load factor passes a threshold (typically 0.66–0.75), the table allocates a larger array and rehashes everything, an O(n) operation. Because the table roughly doubles, this happens rarely enough that the cost per insert averages out to O(1).

When Not to Use One

• You need ordering. Hash tables have none. For sorted iteration, range queries ("all keys between 10 and 50"), or nearest-neighbour lookups, use a balanced BST or a sorted array with binary search. Note that Python dicts preserve insertion order, which is not the same as sorted order.
• Keys must be hashable and immutable. Mutating a key after insertion makes it unfindable.
• Memory matters. Hash tables deliberately stay partly empty; a sorted array is far more compact.
• You need worst-case guarantees. Real-time systems often prefer a tree's predictable O(log n) to a hash table's usual-O(1)-sometimes-O(n).

Related structure worth knowing: a Bloom filter answers "is this key definitely absent, or possibly present?" in constant time and a few bits per element, with no false negatives. It is the standard front-line filter before an expensive disk or network lookup.

Algorithm Selection Guide

When to Use Linear Search:

• Data is unsorted
• Dataset is small (n < 100)
• You only need to search once
• Data structure doesn't support random access

When to Use Binary Search:

• Data is sorted (or can be sorted)
• Dataset is large (n > 100)
• You need to perform multiple searches
• Data structure supports random access
• You need ordered operations a hash table cannot provide: range queries, predecessor/successor, sorted iteration

When to Use a Hash Table:

• You need repeated lookups by exact key and do not care about order — this is the common case, and it beats both algorithms above
• Data is unsorted and sorting it would not pay for itself
• You are de-duplicating, counting, or checking membership

A useful rule of thumb: sorting to enable binary search costs O(n log n) up front, then O(log n) per query. Building a hash table costs O(n), then O(1) per query. For pure equality lookups the hash table wins outright; binary search earns its place when you need order.

Note: For graph traversal and pathfinding algorithms (DFS, BFS, Dijkstra's, Bellman-Ford, Floyd-Warshall, A*), see Graph Algorithms.

What's Next?

Now that you understand fundamental searching algorithms, explore related topics:

• Sorting Algorithms - Learn how to sort data before using binary search
• Trees - Learn about binary search trees and tree-based searching
• Graph Algorithms - Explore graph traversal and pathfinding algorithms (DFS, BFS, Dijkstra's, Bellman-Ford, Floyd-Warshall, A*)