Searching — Informatique universitaire

Vocabulaire

English	Sens
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}

Pratique

Binary search requires —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

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}

Pratique

The worst-case probes for binary search on 16 slots is —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

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 = mid instead of mid + 1 loops forever; in fixed-width languages compute mid as lo + (hi - lo) // 2.

{exercise:uni-cs0507-miss}

Pratique

Searching 43 on the course array probes —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui