🧱 Unit 1 – Data Structures & Algorithms · Lesson 13
Searching: Linear, Binary, Hashing
What is searching?
Searching means finding whether a value (the key) is present in a collection and, if yes, where. We study three methods: linear search, binary search and hashing.
Linear search
Check every element one by one from the start until the key is found or the list ends. It works on unsorted data too.
Python
def linear_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i # position found
return -1 # not found
data = [8, -4, 7, 17, 0, 2, 19]
print('17 found at index', linear_search(data, 17))
print('5 found at index', linear_search(data, 5))17 found at index 3
5 found at index -1
Binary search
Works only on a sorted list. Look at the middle element: if it is the key, stop; if the key is bigger, continue in the right half; otherwise in the left half. Each step halves the search area.
- 1low = 0, high = n-1
- 2mid = (low + high) // 2
- 3key == list[mid] → found
- 4key > list[mid] → low = mid + 1
- 5key < list[mid] → high = mid - 1
- 6Repeat while low <= high; otherwise not found
Python
def binary_search(lst, key):
low, high = 0, len(lst) - 1
step = 0
while low <= high:
mid = (low + high) // 2
step += 1
print('Step', step, ': low', low, 'high', high, 'mid', mid, '->', lst[mid])
if lst[mid] == key:
return mid
elif key > lst[mid]:
low = mid + 1 # search right half
else:
high = mid - 1 # search left half
return -1
nums = [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43]
print('Found at', binary_search(nums, 17))
print('Found at', binary_search(nums, 4))Step 1 : low 0 high 14 mid 7 -> 17
Found at 7
Step 1 : low 0 high 14 mid 7 -> 17
Step 2 : low 0 high 6 mid 3 -> 7
Step 3 : low 0 high 2 mid 1 -> 3
Step 4 : low 2 high 2 mid 2 -> 5
Found at -1
Comparisons: linear vs binary
Python
def count_linear(lst, key):
c = 0
for x in lst:
c += 1
if x == key:
break
return c
def count_binary(lst, key):
low, high, c = 0, len(lst) - 1, 0
while low <= high:
mid = (low + high) // 2; c += 1
if lst[mid] == key: break
if key > lst[mid]: low = mid + 1
else: high = mid - 1
return c
big = list(range(1, 1001)) # 1..1000 sorted
for k in [1, 500, 1000]:
print('key', k, '| linear:', count_linear(big, k), '| binary:', count_binary(big, k))key 1 | linear: 1 | binary: 9
key 500 | linear: 500 | binary: 1
key 1000 | linear: 1000 | binary: 10
Hashing
Hashing stores each key at a position calculated by a hash function, e.g. key % size. To search we compute the same position and look there once – no scanning.
Python
SIZE = 10
table = [None] * SIZE
def h(key):
return key % SIZE # hash function: remainder method
for k in [34, 16, 2, 93, 80, 77]:
table[h(k)] = k
print(table)
def hash_search(key):
return table[h(key)] == key # only ONE look-up
print(93, hash_search(93))
print(45, hash_search(45))[80, None, 2, 93, 34, None, 16, 77, None, None]
93 True
45 False
Collisions
Python
# Collision: two keys get the same position
SIZE = 10
print('h(23) =', 23 % SIZE, ' h(43) =', 43 % SIZE)
# Simple fix: chaining – keep a small list at every slot
table = [[] for _ in range(SIZE)]
for k in [23, 43, 15, 33]:
table[k % SIZE].append(k)
print(table[3], table[5])h(23) = 3 h(43) = 3
[23, 43, 33] [15]
Python dictionary as hash table
Python
# Python dict is a ready-made hash table
phone = {'Asha': '98110', 'Ravi': '98220', 'Neha': '98330'}
name = 'Ravi'
print(name, '->', phone.get(name, 'not found'))
print('Zoya ->', phone.get('Zoya', 'not found'))Ravi -> 98220
Zoya -> not found
Summary
| Linear | Binary | Hashing | |
|---|---|---|---|
| Needs sorted data? | No | Yes | No |
| Worst case | n comparisons | about log₂n | 1 (no collision) |
| Best for | Small / unsorted lists | Large sorted lists | Fast look-up by key |
Frequently Asked Questions
What is the condition for binary search?
The list must be sorted. Binary search compares the key with the middle element and discards half of the list each time.
How many comparisons does binary search need for 1000 elements?
At most about 10, because 2^10 = 1024. Linear search may need 1000.
What is a collision in hashing?
When two different keys produce the same hash value (position). It is resolved by methods such as chaining or probing.
