Searching
Linear · Binary · JumpFinding a value is one of the most common jobs a program does. Linear search checks elements one by one. If the array is sorted, binary search looks in the middle and throws away half of the array with every comparison — 1,000,000 elements need only about 20 steps.
- Linearcheck every element — any array
- Binaryhalve the range — sorted array only
- Jumpskip √n at a time, then walk
- Being compared
- Found
- Still possible
- Ruled out
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Why sorting changes everything
In an unsorted array a value could be anywhere, so the only safe method is to look at every element. In a sorted array one comparison tells you which SIDE the value must be on — everything on the other side can be ignored. That single idea turns O(n) into O(log n).
// unsorted: 42 could be anywhere
int a[] = { 17, 3, 58, 42, 8 };
// sorted: compare with the middle (17)
int b[] = { 3, 8, 17, 42, 58 };
// 42 > 17 → only { 42, 58 } is left
Linear search
- Start at index 0.
- Compare each element with the key.
- Stop as soon as it matches.
- Reached the end? Return −1.
Binary search
- low = 0, high = n − 1.
- mid = the middle of low…high.
- Equal → found. Key larger → low = mid + 1. Smaller → high = mid − 1.
- low > high → not found.
Jump search
- Pick a block size of √n.
- Check the last element of each block.
- Stop at the first block whose last element ≥ key.
- Walk through that block one by one.
Halving is powerful
- 16 elements → at most 5 binary steps.
- 1,000 elements → about 10 steps.
- 1,000,000 elements → about 20 steps.
- log₂ n grows very slowly.
A classic bug
- mid = (low + high) / 2 can overflow for huge arrays.
- Safer: mid = low + (high − low) / 2.
- Use low <= high (not <) in the loop.
- Move to mid ± 1, never to mid — or it may loop forever.
Which one to use?
- Small or unsorted array → linear.
- Sorted array with fast index access → binary.
- Sorted, but jumping back is costly → jump search.
- Many searches? Sort once, then binary search.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of elements. All three searches use O(1) extra space (recursive binary search uses O(log n) for the call stack).
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Linear search | O(1) |
O(n) |
O(n) |
Grows with n |
| Binary search | O(1) |
O(log n) |
O(log n) |
Grows with n |
| Jump search | O(1) |
O(√n) |
O(√n) |
Grows with n |
| Sort first, then binary search | O(n log n) |
O(n log n) |
O(n log n) |
Grows with n |
Worst-case comparisons
| Array size n | Linear (n) | Jump (≈ 2√n) | Binary (≈ log₂ n) |
|---|---|---|---|
| 16 | 16 | 8 | 5 |
| 1,000 | 1,000 | 63 | 10 |
| 1,000,000 | 1,000,000 | 2,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 63,246 | 30 |
The three methods side by side
| Linear | Binary | Jump | |
|---|---|---|---|
| Needs a sorted array? | No | Yes | Yes |
| Needs jumping to any index? | No | Yes | Yes (but only forwards) |
| Time (worst) | O(n) | O(log n) | O(√n) |
| Works on a linked list? | Yes | Poorly — no direct access to the middle | Poorly |
Check your understanding
Answer each question — you will see the explanation straight away.
Which search can be used on an UNSORTED array?
Only linear search. Binary and jump search rely on the order of the elements to skip parts of the array.
Binary search on [3, 8, 12, 17, 21, 25, 30]: which element is compared first?
low = 0, high = 6, so mid = 3 and arr[3] = 17 is compared first.
In binary search, arr[mid] is SMALLER than the key. What happens next?
The key must be to the right of mid, so the left half (including mid) is thrown away: low = mid + 1.
About how many comparisons does binary search need in the worst case for 1,000,000 sorted elements?
Each step halves the range: 2²⁰ ≈ 1,000,000, so about 20 steps are enough.
What block size does jump search use for an array of n elements?
Jumping √n at a time, then walking at most √n inside one block, gives about 2√n steps in total.
When does binary search stop and report "not found"?
low > high means the range of possible positions is empty.
Searching quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.