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

1. Linear Search

The simplest searching algorithm that sequentially checks each element in a list until it finds the target value.

Time Complexity: O(n) worst/average, O(1) best
Space Complexity: O(1)
Best For: Unsorted data, small datasets
Prerequisites: None

2. Binary Search

An efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.

Time Complexity: O(log n)
Space Complexity: O(1) iterative, O(log n) recursive
Best For: Sorted data, large datasets
Prerequisites: Understanding of sorted arrays (see Sorting Algorithms)

Algorithm Comparison

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

Algorithm	Data Structure	Time Complexity	Space Complexity	Best Use Case
Linear Search	Array/List	O(n)	O(1)	Unsorted data, small datasets
Binary Search	Sorted Array	O(log n)	O(1) iterative, O(log n) recursive	Sorted arrays, large datasets

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

Operation	Average	Worst Case
Insert	O(1) amortized	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

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.

Beyond the Basics: Search Techniques Worth Knowing

Linear and binary search cover the elementary cases, and hash tables cover most of the "look up by key" applications. Real systems use several more specialised search techniques for cases those three do not handle well.

Interpolation Search

Binary search assumes nothing about the data other than that it is sorted. If you additionally know that the data is roughly uniformly distributed, you can do better. Interpolation search estimates where the target should be based on its value rather than always going to the middle, the way a person searches a phone book. Looking for "Smith" you do not open to the middle of the alphabet; you open near the end, because you know from experience where S falls in the distribution.

Interpolation search on uniformly distributed data runs in O(log log n), asymptotically faster than binary search. On non-uniform data it degrades to O(n), so it is used only when the distribution is known and roughly uniform. Typical applications: searching numeric arrays with predictable ranges (timestamps, sensor readings, IP addresses within an allocated block), searching dictionaries in most natural languages where letter frequency is well-understood.

Exponential Search (Galloping Search)

Useful when the array is very large or infinite, or when the target is expected near the beginning. Instead of starting from index n/2 as binary search does, exponential search starts at index 1 and doubles the position until it either finds the target or overshoots it, then runs a binary search on the identified interval. Total complexity is O(log i) where i is the target's position, strictly better than binary search's O(log n) when i is small.

Exponential search is the basis of Timsort's "galloping mode," which kicks in during merges when one of the runs is winning many consecutive comparisons in a row. It also appears in string search algorithms for finding the pattern's location in the text when you have a good hint about where it might be.

Fibonacci Search

A binary-search variant that divides the array according to Fibonacci numbers instead of powers of two. This has one very specific advantage: it uses only addition and subtraction to compute the split points, no division. On CPUs where division is slow (some embedded processors, some GPUs), Fibonacci search can be faster than binary search despite the same O(log n) complexity. It is largely a historical curiosity on modern x86, where integer division is cheap enough that the constant factor differences vanish.

Ternary Search

Split into thirds instead of halves. Used specifically for finding the maximum (or minimum) of a unimodal function, a function that increases and then decreases, where binary search cannot apply because there is no total order on candidate values. Ternary search on a unimodal function converges to the extremum in O(log n) iterations of the interval. Common in competitive programming problems involving physics simulations, optimisation, or peak detection.

Jump Search

A middle ground between linear and binary search: step through the sorted array in fixed-size jumps of √n elements, then do a linear scan within the block that contains the target. Complexity O(√n), asymptotically worse than binary search, but sometimes faster in practice on data structures where random access is expensive (linked lists with skip-list overlays, some disk-based data structures).

Substring Search

Searching for a pattern within a text is a completely different problem from searching for an element in an array, and it has its own family of algorithms: Rabin-Karp (rolling hash), Boyer-Moore (skip based on last-character heuristic), KMP (failure function), and the Z-algorithm are the standard members. These are covered separately in the string algorithms chapter.

Python's `bisect` Module

Rather than writing binary search yourself, Python's standard library provides the bisect module, which offers correct binary-search primitives:

import bisect

sorted_list = [1, 3, 5, 7, 9, 11]

# Find insertion point (leftmost)
bisect.bisect_left(sorted_list, 5)      # 2 (before the existing 5)
bisect.bisect_right(sorted_list, 5)     # 3 (after the existing 5)
bisect.bisect(sorted_list, 5)           # 3 (alias for bisect_right)

# Insert while maintaining sorted order
bisect.insort(sorted_list, 6)           # list becomes [1, 3, 5, 6, 7, 9, 11]

# Check if value is present (bisect_left + verify)
def contains(arr, x):
    i = bisect.bisect_left(arr, x)
    return i < len(arr) and arr[i] == x

bisect is implemented in C, is provably correct, handles all the edge cases correctly, and is faster than any hand-written Python version. Reach for it every time you want binary search in Python code. The equivalent in other languages: C++'s std::lower_bound / std::upper_bound, Java's Collections.binarySearch, Rust's slice binary_search. All are correct and fast; none of them require you to write the algorithm yourself.

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*)

Searching Algorithms

Introduction to Searching

Searching Algorithms

1. Linear Search

2. Binary Search

Algorithm Comparison

Hash Tables: The O(1) Option

Collisions

Complexity

When Not to Use One

Beyond the Basics: Search Techniques Worth Knowing

Interpolation Search

Exponential Search (Galloping Search)

Fibonacci Search

Ternary Search

Jump Search

Substring Search

Python's bisect Module

Algorithm Selection Guide

When to Use Linear Search:

When to Use Binary Search:

When to Use a Hash Table:

What's Next?

Python's `bisect` Module