Linear search walks through a list one item at a time until it finds the target (or runs out). Simple and works on any list, sorted or not. Its speed is O(n).
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i # found! return the index
return -1 # not found
print(linear_search([5, 3, 9, 1], 9)) # 2
⚡ Binary search — halve it every time
Binary search only works on a sorted list, but it's lightning fast — O(log n). It checks the middle, then throws away half the list every step.
It's exactly how you find a word in a dictionary: open the middle, decide "earlier" or "later", and repeat on the half that remains.
def binary_search(items, target):
low = 0
high = len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
low = mid + 1 # target is in the right half
else:
high = mid - 1 # target is in the left half
return -1
🤯 Why halving is a superpower
Searching a sorted list of 1,000,000 items:
Method
Worst-case steps
Big-O
Linear search
1,000,000
O(n)
Binary search
about 20
O(log n)
💡 The catch
Binary search needs the list to be sorted first. If you only search once, sorting may not be worth it. If you search many times, sort once and enjoy fast lookups forever.
✅ What you learned
Linear search: check every item, O(n), works on any list.
Binary search: halve the range each step, O(log n), needs a sorted list.
Return the index when found, or -1 when not.
The midpoint is (low + high) // 2.
🎮 Time to Practice!
Build both searches and feel the speed difference. 🔍
🚶
Task 1: Linear Search
Easy
Finish linear_search to return the index of target, or -1 if missing. Searching for 9 in [5, 3, 9, 1] should print 2.
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i
return -1
print(linear_search([5, 3, 9, 1], 9))
⚡
Task 2: Binary Search
Tricky
Complete the binary search loop. The list is sorted. Update low or high based on the middle value. Searching for 11 in [1, 3, 5, 7, 11, 13] should print 4.
Binary search on [2, 4, 6, 8, 10, 12, 14] for 8. The middle is index 3 — so it's found in just 1 step! Run the code to confirm it prints Found at index 3 then Steps: 1.
🏋️ Extra Practice — Algorithm Reps
Searching is the algorithm you will use most in your life. Drill both kinds until binary search feels automatic.
🥇
Task 4: Find the Smallest
Easy
Write index_of_min(items) that returns the position of the smallest value — scanning once, O(n). Print it for [7, 2, 9, 1, 5] (answer: 3) and for [4].
3
0
def index_of_min(items):
best = 0
for i in range(1, len(items)):
if items[i] < items[best]:
best = i
return best
print(index_of_min([7, 2, 9, 1, 5]))
print(index_of_min([4]))
📊
Task 5: Count the Comparisons
Medium
Write binary_steps(items, target): a binary search that counts how many times it looks at a middle value. Print the count for finding 999 in list(range(1000)), then for finding 0. Both should be small — that is the power of halving.
Binary search works on anything that can be ordered — including words. Write find_word(words, target) using binary search on the sorted list ["ant", "bee", "cat", "dog", "eel"] and print the index of "dog" and of "fox" (missing → -1).
Write insert_position(items, value) that returns the index where value should be inserted to keep the list sorted — using binary search. For [1, 3, 5, 7] print the position for 4 (answer 2), for 0 and for 9.
Write find_all(items, target) that returns a list of every index where the target appears. Print it for [3, 1, 3, 7, 3] looking for 3, and for a value that is missing.
[0, 2, 4]
[]
def find_all(items, target):
found = []
for i, item in enumerate(items):
if item == target:
found.append(i)
return found
print(find_all([3, 1, 3, 7, 3], 3))
print(find_all([3, 1, 3, 7, 3], 8))
🎯
Task 9: Boss Level: The Guessing Robot
Boss
A robot must guess a secret number from 1 to 1000 using binary search. Write a loop that always guesses the middle of the range, prints each guess, and narrows the range until it finds secret = 731. Print how many guesses it needed at the end — it should be about 10, not 731!