Searching
A linear search checks each item from the start until the target is found or the list ends. It works on any list, ordered or not, but can be slow for long lists.
A binary search is much faster but the list must already be sorted. It checks the middle item, then discards the half that cannot contain the target, and repeats.
Key idea
Binary search only works on a sorted list; linear search works on any list. Binary search halves the search area each step, so it needs far fewer comparisons.
Sorting
A bubble sort compares each pair of neighbouring items and swaps them if they are in the wrong order. Each full pass pushes the largest remaining value to the end. Passes repeat until a pass makes no swaps.
An insertion sort takes each item in turn and inserts it into its correct place among the items already sorted to its left.
Example
Bubble sort on 5, 2, 4 — first pass: compare 5 and 2 → swap to 2, 5, 4; compare 5 and 4 → swap to 2, 4, 5. The list is now sorted.
Remember
- Binary search needs a sorted list first.
- Bubble sort works in passes and repeats until no swaps occur.
- Insertion sort builds a sorted section one item at a time.