Algorithms · Hub
Seven ways to find something in an array. Linear search works on anything in $O(n)$. The others use order (sorted, rotated, evenly spread, or hill-shaped) to throw away big parts of the array with each comparison and reach $O(\log n)$ or better.
Why it matters: the question "what do I know about my data?" decides the speed. The same lookup can take a million comparisons or twenty.
Answer each one out loud before opening the sample answer.
| Algorithm | Best | Average | Worst | Data requirement |
|---|---|---|---|---|
| Linear | $O(1)$ | $O(n)$ | $O(n)$ | None |
| Binary | $O(1)$ | $O(\log n)$ | $O(\log n)$ | Sorted |
| Interpolation | $O(1)$ | $O(\log \log n)$ | $O(n)$ | Sorted, uniform |
| Exponential | $O(1)$ | $O(\log i)$ | $O(\log n)$ | Sorted, size may be unknown |
| Ternary | $O(1)$ | $O(\log n)$ | $O(\log n)$ | Sorted, or unimodal function |
| Rotated array | $O(1)$ | $O(\log n)$ | $O(\log n)$ | Rotated sorted, distinct |
| Peak finding | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | None |
Check every element in order until you find it.
O(n) worst · any order · O(1) space
StudyCheck the middle, throw away half, repeat.
O(log n) worst · sorted · O(1) space
StudyGuess the position from the value, like a phone book.
O(log log n) avg · O(n) worst · sorted + uniform
StudyDouble the index to bracket the target, then binary search.
O(log i) · sorted · unknown size OK
StudyTwo probes, keep one third; best for hill-shaped functions.
O(log n) · sorted or unimodal · more comparisons than binary
StudyOne half is always sorted: test the target against it.
O(log n) · rotated sorted · distinct values
StudyWalk uphill from the middle to reach a local peak.
O(log n) · any array · finds a peak, not the max
Study
flowchart TD
A{"Looking for a value, or a peak?"} -->|"a peak / maximum of a hill"| P{"Array or function?"}
P -->|array| PF["Peak finding"]
P -->|"unimodal function"| T["Ternary search"]
A -->|"a value"| B{"Is the data sorted?"}
B -->|no| L["Linear search"]
B -->|"sorted but rotated"| R["Rotated array search"]
B -->|yes| C{"Size unknown, or target near the front?"}
C -->|yes| E["Exponential search"]
C -->|no| D{"Values evenly spread?"}
D -->|yes| I["Interpolation search"]
D -->|"no / not sure"| BS["Binary search"]
Videos
Come back after 3, 7, 14, then 30 days. Spacing beats cramming.
Explain this topic in your own words, as if teaching a beginner.
Explain it in your own words first, then record a 2–3 minute video on your phone.
25:00
Time's up.
Ready to record? Open your phone camera now and record a 2–3 minute explanation.
Saved only in this browser (localStorage). Nothing is uploaded.