Searching means finding the thing we want. Sorting means putting things in a useful order. We often sort first so searching becomes easier.
Linear search checks one by one
You lost a red block in a toy box. You pick up each toy until you find it. That is linear search. It works even when the toys are messy, but the red block might be the very last thing you check.
For blue, yellow, red, green, we check blue, then yellow, then red. Found it! We needed three checks.
Binary search cuts the pile in half
Binary search is faster, but the items must already be sorted. Think of finding a word in a dictionary. You open near the middle. If your word comes earlier, you ignore the right half. Then you cut the smaller part in half again.
Every check throws away half of the places where the answer could be. That is why binary search stays quick even when the list is big.
Bubble sort swaps neighbors
One simple sorting method is bubble sort. Compare two neighbors. If the left one is bigger, swap them. Keep doing this across the row. Large values slowly move to the end like bubbles floating up.
- Start with 3, 1, 2.
- Swap 3 and 1 to get 1, 3, 2.
- Swap 3 and 2 to get 1, 2, 3.
- The row is now sorted.
Bubble sort is easy to learn, but it can do lots of work. Real programs often use smarter sorts. The important idea is that order can make later jobs easier.
toys = ["blue", "yellow", "red", "green"]
for index, toy in enumerate(toys):
if toy == "red":
print("Found red at", index)
break
numbers = [3, 1, 2]
for end in range(len(numbers) - 1, 0, -1):
for index in range(end):
if numbers[index] > numbers[index + 1]:
numbers[index], numbers[index + 1] = numbers[index + 1], numbers[index]
print(numbers) # [1, 2, 3]Your tiny challenge
Write five numbers on cards. Find one with linear search. Then sort the cards and find one by repeatedly choosing the middle. You have tried both search styles.