Search, Hashing, and Choosing a Structure
Finding one member by ID differs from finding every member whose ID is between 100 and 200. Ask whether you need an exact key, an ordering, or a range.
Halve a sorted array’s search range
Binary search compares the middle value and discards half the remaining range. The array must already be sorted.
def binary_search(values, target):
left, right = 0, len(values) - 1
while left <= right:
mid = (left + right) // 2
if values[mid] == target:
return mid
if values[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search([4, 9, 15, 22, 31], 22))
print(binary_search([4, 9, 15, 22, 31], 10))
The outputs are index 3 and -1, meaning not found. An empty array skips the loop and returns -1. Search takes O(log n), but unsorted data requires a separate sorting step first.
Calculate a storage location from a key
A hash function turns a key into a hash value, which a hash table uses to choose a slot. With key % 4, both 3 and 7 reach slot 3. Different keys reaching the same slot cause a collision.
- Chaining: Keep the items belonging to a slot in a separate linked collection.
- Open addressing: Follow a rule to find another free slot within the table.
- Lookups must compare the actual key as well as its hash.
Python’s dict and set use hash tables. With suitably distributed hashes, lookup is average O(1), but heavy collisions can produce O(n) worst-case time. These costs assume hashing and comparing a key take constant time.
Final exercise: Design a small service
Which structures would you choose for these music-app features?
- Find a song title by its ID.
- Remove queued songs in registration order.
- Undo recent edits one at a time.
- Run scheduled tasks with the nearest start times first.
- Represent friendships between users.
Show explanation
- A hash table, such as
dict, maps song IDs to titles. - A queue removes the earliest registered song first.
- A stack reverses the latest edit first.
- A heap implements the priority queue.
- A graph represents connections among users.
Choices can change with data size and additional requirements. The essential habit is to describe frequent operations and required ordering first, then choose an implementation that supports them.
Continue with the algorithms course to study problem-solving strategies.