What are searching and sorting algorithms?
An algorithm is a list of clear steps to solve a problem. Two jobs come up again and again in computing:
- Searching: is a value in the list, and where?
- Sorting: put the list in order, smallest to largest (ascending) or largest to smallest (descending).
We compare algorithms by counting comparisons (how many times we check two values). Fewer comparisons means a faster algorithm, especially for big lists.
Linear search
Start at the first item. Compare it with the target. If it matches, stop. If not, move to the next. If you reach the end, the item is not there.
for i from 0 to length − 1
if list[i] = target then return i
return "not found"- Works on any list, sorted or not.
- Simple to write.
- Slow for big lists: a list of n items may need n comparisons (worst case).
Binary search
Binary search only works on a sorted list.
- Look at the middle item.
- If it is the target, stop.
- If the target is smaller, keep only the left half; if bigger, keep only the right half.
- Repeat on the half that is left until found, or nothing is left.
low ← 0, high ← length − 1
while low ≤ high
mid ← (low + high) DIV 2
if list[mid] = target then return mid
else if list[mid] < target then low ← mid + 1
else high ← mid − 1
return "not found"Each check halves the list. 1,000 items need at most about 10 checks; 1,000,000 items about 20. Linear search could need 1,000,000.
Bubble sort and merge sort
Bubble sort
Go through the list comparing each pair of neighbours; swap them if they are in the wrong order. After one pass, the biggest item has reached the end. Repeat passes until a pass makes no swaps. Easy to code, uses little extra memory, but slow on big lists (about n² comparisons).
Merge sort
A divide and conquer method. Split the list in half again and again until each piece has one item (one item is already sorted). Then merge pairs of pieces: compare the front items of the two pieces and take the smaller one each time. Much faster on big lists (about n·log₂n comparisons) but needs extra memory for the merged lists.
Insertion sort (also common)
Take items one by one and slide each into its correct place in the sorted part, like arranging playing cards in your hand. Good for small or nearly sorted lists.
Choosing an algorithm
| Algorithm | Needs sorted list? | Speed on big lists | Best for |
|---|---|---|---|
| Linear search | No | Slow (n) | Small or unsorted lists |
| Binary search | Yes | Very fast (log₂n) | Big sorted lists |
| Bubble sort | — | Slow (n²) | Tiny or nearly sorted lists, learning |
| Merge sort | — | Fast (n log n) | Big lists |
Tip: if you will search a list many times, sorting it once and then using binary search saves time overall.
Try it: card search race
Write the numbers 1–16 on cards. Shuffle them face down in a row and ask a friend to find 11 by turning one card at a time (linear search). Count the turns. Now lay them in order and find 11 by always turning the middle card (binary search). Which needed fewer turns? Then sort a shuffled set by bubble sort, counting your swaps.
Key formulas and definitions
- Linear search worst case: n comparisons
- Binary search worst case: about log₂n + 1 comparisons
- mid = (low + high) DIV 2
- Bubble sort: up to n − 1 passes, about n²/2 comparisons
- Merge sort: about n·log₂n comparisons
Worked examples
1. Linear search for 56 in [42, 7, 19, 88, 3, 56]. How many comparisons?
42, 7, 19, 88, 3, 56 → found at the 6th check: 6 comparisons.
2. Binary search for 64 in [3, 7, 11, 19, 23, 35, 42, 56, 64, 71, 88, 90]. Show the middles.
low 0, high 11 → mid 5 = 35 < 64 → low 6. mid 8 = 64 → found. 2 comparisons.
3. One pass of bubble sort on [5, 1, 4, 2].
5>1 swap → [1,5,4,2]; 5>4 swap → [1,4,5,2]; 5>2 swap → [1,4,2,5]. The 5 is now at the end.
4. Merge [2, 9] and [4, 5].
2 vs 4 → take 2; 9 vs 4 → take 4; 9 vs 5 → take 5; then 9. Result [2, 4, 5, 9].
5. At most how many checks does binary search need for 64 items?
64 → 32 → 16 → 8 → 4 → 2 → 1: 6 halvings, so at most 7 checks.
6. Why can't binary search be used on [9, 2, 7, 4]?
The list is not sorted, so throwing away a half might throw away the target. Sort first or use linear search.
Common mistakes
- Using binary search on an unsorted list.
- Stopping bubble sort after one pass. You must repeat until a pass makes no swaps.
- Thinking binary search is always better: for a tiny or unsorted list, linear search can be simpler and quicker.
- In merge sort, joining halves without comparing (just putting one after the other).