Introduction
Searching is the task of determining whether a target value exists in a collection and, if so, locating it. The right search strategy depends on whether the data is sorted, how often it changes, and whether auxiliary data structures like hash tables are available. This topic compares linear search, binary search, and hash-table lookup to clarify when each is the best tool.
Cricket analogy: Finding whether a specific player's name appears on a huge unsorted scorecard versus a sorted alphabetical roster versus an indexed database determines whether you scan every entry, use a sorted lookup, or a hash-based player registry.
Algorithm/Syntax
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
def hash_lookup(d, target):
# d is a dict built once: O(n) to build, O(1) average per lookup
return target in dExplanation
Linear search checks each element in sequence until it finds the target or exhausts the array; it requires NO precondition (works on unsorted data) and runs in O(n) time, O(1) space. It is the only option for unsorted, unindexed data or for data structures without random access, like singly linked lists (where you can't jump to a middle element in O(1)). Binary search requires sorted data but achieves O(log n) time by halving the search space each step. Hash-table lookup (Python dict/set) offers O(1) average time by mapping keys to array indices via a hash function, but has O(n) worst-case time under heavy hash collisions, requires O(n) extra space for the hash table, and does not support range queries (e.g., 'find all values between 10 and 20') or order-based queries the way a sorted array does.
Cricket analogy: Scanning every ball of an unsorted highlights reel for a six is linear search's O(n), needing no prior sorting and working even on a disorganized archive, while flipping through a sorted run-tally halves the search each time like binary search, and a hashed player-stats lookup returns Kohli's average in O(1) average time but can't answer 'all players averaging between 40 and 50' without extra structure.
Example
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
data = [17, 4, 23, 1, 8]
print(linear_search(data, 23)) # 2, works on unsorted data, O(n)
sorted_data = sorted(data) # [1, 4, 8, 17, 23]
print(binary_search(sorted_data, 23)) # 4, requires sorted input, O(log n)
lookup_set = set(data)
print(23 in lookup_set) # True, O(1) average via hashingOutput
For a target near the end of an unsorted 1,000,000-element array, linear search performs up to 1,000,000 comparisons, binary search on the sorted version performs at most ~20 comparisons (log2(1,000,000) ≈ 20) but requires the O(n log n) upfront sort cost if not already sorted, and a hash set performs roughly 1 comparison on average after an O(n) build. If only a single lookup is needed on unsorted data, linear search's O(n) beats paying O(n log n) to sort first just for binary search; if many repeated lookups are needed, sorting once (or building a hash set once) amortizes the upfront cost across all queries.
Cricket analogy: Finding one player's stat card in a stack of a million unsorted scorecards by checking each is linear search's up to a million checks, sorting the stack first then binary-searching costs about 20 checks plus the sort, while a hashed player registry averages one lookup after building it once — worth it only if you'll query many players, not just one.
Key Takeaways
- Linear search: O(n) time, O(1) space, no preconditions, works on any iterable including linked lists.
- Binary search: O(log n) time, O(1) space, requires sorted, random-access data.
- Hash lookup: O(1) average time, O(n) space, no ordering support, requires hashable keys and good hash distribution.
- Choose based on data mutability, need for order/range queries, and number of repeated lookups amortizing setup cost.
Practice what you learned
1. Which search algorithm works correctly on unsorted data without any preprocessing?
2. What is the average-case time complexity of a hash-table lookup?
3. What is a key limitation of hash tables compared to a sorted array for searching?
4. Why might linear search be preferable to binary search for a single one-off lookup on unsorted data?
5. What is the worst-case time complexity of a hash-table lookup?
Was this page helpful?
You May Also Like
Binary Search
The classic O(log n) algorithm for finding a target in a sorted array using repeated halving, with correct boundary handling.
Hash Tables
A data structure that maps keys to values using a hash function for near-constant time lookups, insertions, and deletions.
Collision Handling in Hashing
Techniques like chaining and open addressing that resolve situations where two different keys hash to the same bucket.