Searching means finding whether a value is in a list, and where. Two common methods are linear search and binary search.
Linear search
Linear search checks each item in turn from the start until it finds the target or reaches the end. It works on any list, sorted or not. If the list has 8 items, it may need up to 8 checks.
Binary search
Binary search is much faster but has one requirement: the list must be sorted first. It looks at the middle item, then throws away the half that cannot contain the target, and repeats. Each step halves the number of items left to check.
Key idea
Linear search: works on any list, checks items one by one. Binary search: needs a SORTED list, and halves the range each step. If the middle is too small, search the right half; if too big, search the left half.
Example
Search for 7 in the sorted list 1 3 5 7 9 11 13. The middle is 7 — found in one step. Search for 3: middle is 7 (too big), take the left half 1 3 5; new middle is 3 — found in two steps. Linear search would have taken 2 checks for 3 as well, but for a list of 1000 items binary search needs about 10 checks while linear may need 1000.
Remember
- Binary search only works on a sorted list.
- Binary search halves the search range each step.
- Linear search works on unsorted lists but is slower.