Searching
Đã giới thiệu
Từ vựng
| English | Ý nghĩa |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | Checking items in sequence until the required item is found or the list ends. |
| binary search/ˈbaɪnəri sɜːtʃ/ | A search of ordered data that repeatedly compares with the middle item and discards half of the remaining search range. |
English
Two ways to look
- Linear search walks the array: $O(n)$, no preconditions. Binary search halves a sorted range: compare the middle, keep one half — sorted is a precondition, not a preference.
{exercise:uni-cs0507-two}
Luyện tập
Binary search requires —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
The halving argument collapses on unsorted data — wrong answers, silently.
English
The probe bound
- Each probe halves the candidates: after $k$ probes at most $\lceil n / 2^k \rceil$ remain, so the worst case is $\lceil \log_2(n+1) \rceil$ probes — $5$ for $n = 16$.
- On the sorted array $[3, 7, \ldots, 63]$ (16 slots), searching $43$ probes indices $7, 11, 9, 10$ — values $31, 47, 39, 43$: four probes, found at index $10$. Linear would walk $11$ values to the same slot.
{exercise:uni-cs0507-bound}
Luyện tập
The worst-case probes for binary search on 16 slots is —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Ceiling of log2 of 17 is 5: each probe halves what remains.
English
The miss that proves the bound
- Search $64$ (absent, above the end): binary probes $7 (31), 11 (47), 13 (55), 14 (59), 15 (63)$ — five probes, then the empty range reports absent. Linear walks all $16$ for the same answer.
- Classic traps: binary search on unsorted data returns wrong answers silently; updating
lo = midinstead ofmid + 1loops forever; in fixed-width languages compute mid aslo + (hi - lo) // 2.
{exercise:uni-cs0507-miss}
Luyện tập
Searching 43 on the course array probes —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Mid 7 reads 31 (go right), mid 11 reads 47 (go left), mid 9 reads 39, mid 10 finds.