Searching Algorithms
Introduced| English |
|---|
| Searching/ˈsɜːtʃɪŋ/ |
| linear search/ˈlɪnɪə sɜːtʃ/ |
| binary search/ˈbaɪnəri sɜːtʃ/ |
| sorted/ˈsɔːtɪd/ |
Finding a value
- Searching 查找 means locating a target value in a collection.
- Two standard algorithms: linear search 线性查找 and binary search 二分查找.
- Both return the index where the target sits — or a "not found" signal (often
-1). - Which one you may use depends on whether the data is sorted.
Linear search
- Check each element from the start, one by one, until you find the target.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Works on any array — sorted or not.
- Worst case: it looks at every element (
nchecks).
Binary search
- Needs a sorted 已排序 array. Look at the middle element each time.
- If the middle is the target, done. If the target is smaller, search the left half; if larger, the right half.
- Each step halves the range that's left to search.
- Far faster on large sorted arrays — about
log₂ nchecks, notn.
Why binary search is fast
- Linear search of a million items: up to a million checks.
- Binary search of a million sorted items: about 20 checks.
- The catch: the array must already be sorted.
- Halving repeatedly is the big idea behind
O(log n).
Binary search only works on a SORTED array — running it on unsorted data gives wrong answers. It also compares to the middle and throws away half the range each step; a linear search compares from the start and drops just one element. If you're not sure the data is sorted, you must use linear search (or sort first).
Binary search for 7 in [1, 3, 5, 7, 9]:
- Middle is
5(index 2). 7 > 5, so search the right half. - Right half is
[7, 9]; middle is7. Found at index 3. - Two checks instead of four — the range halved each time.
Linear search checks elements from the start (works on any array, up to n checks). Binary search needs a sorted array, compares to the middle, and halves the search range each step (about log₂ n checks). Both return the index found, or a "not found" signal like -1.
Linear vs binary search
Binary search halves the sorted range each step.
A linear search...
Linear = start to end; works on any array.
Binary search requires the array to be...
Binary search only works on sorted data.
Each step of binary search...
It compares to the middle and keeps one half.
Binary search in [1,3,5,7,9] for 7: how many comparisons (middle each time)?
Compare to 5, then to 7 — two comparisons.
Binary search gives correct results on an UNSORTED array.
It relies on order; unsorted data breaks it.
Match each search to its property.
Linear is general but slower; binary is fast but needs order.