Searching Algorithms
Finding a value in a list can take very little time or many checks, depending on the algorithm. Enter a list of numbers and a target value. Then watch how each algorithm searches for it. Values that are still possible remain highlighted, while values that are no longer relevant fade away. This helps you see how each method reduces the search area.
Interactive workspace
Checks the middle value of a sorted list. It then removes the half that cannot contain the target and repeats the process.
Enter whole numbers from 0 to 99, separated by spaces. Up to 20 numbers.
Examples
Binary search needs sorted data, and this list already is.
The list
Step 0 of 3
Looking for
11
Press Next or Play. The search starts here.
- 1
1
- 3
2
- 5
3
- 7
4
- 9
5
- 11
6
- 13
7
- 15
8
Comparisons
0
Still possible
8
of 8 positions
Looked at
0
Step
0/3
Step-by-step explanation
0 of 3 steps
Press Next or Play to see how the algorithm checks each position and narrows down the search.
Same list and target, every algorithm
| Algorithm | Comparisons | Result | Average time | Sorted list |
|---|---|---|---|---|
| 6 | position 6 | O(n) | Not needed | |
| 2 | position 6 | O(log n) | Required | |
| 4 | position 6 | O(√n) | Required | |
| 1 | position 6 | O(log log n) if evenly spread | Required |
Positions refer to the list each algorithm searched: sorted for binary, jump and interpolation, as typed for linear.
Under the hood
From input to screen
The experiment follows this process. Select any box to see what it does and which function or component is behind it.
Pipeline: input, parsing, simulation, steps, visualization
Click any box to see what it does and why it is built that way.
Start
Input
- What it does
- You enter a list of numbers and a target value, then select Linear, Binary, Jump or Interpolation Search.
- Where it lives
- SearchingDemo.tsx (text, targetText, algo)
- Why it is built this way
- Only the list, target and selected algorithm are stored. The rest is calculated from them.
Technical notes
How Searching Algorithms works
How the algorithm works
The simulator checks the list one position at a time, depending on the selected algorithm. Each check is saved as a step. The step shows which position was checked, which part of the list is still possible and why the search moves forward.
Linear Search checks values one by one and works with sorted or unsorted lists. Binary Search checks the middle value and removes half of the search area. Jump Search moves through the list in fixed-size jumps, then checks the relevant section. Interpolation Search estimates where the target should be based on the values, so it works especially well when values are evenly spread. Binary, Jump and Interpolation Search need sorted data. If you enter an unsorted list, the simulator sorts it first and tells you that it has done so.
Important steps
- 01Check the list and target. The list can contain up to 20 whole numbers from 0 to 99.
- 02Sort the list first if the selected algorithm requires sorted data.
- 03Choose the next position to check.
- 04Compare that value with the target.
- 05Reduce the search area based on the result.
- 06Stop when the target is found or no possible positions remain.
- 07Compare all four algorithms using the same input.
Relevant variables
- n
- Number of values, up to 20.
- target
- The value being searched for.
- lo, hi
- First and last positions that may still contain the target.
- probe
- The position checked in the current step.
- comparisons
- Number of positions checked so far.
Time and space complexity
| Algorithm | Time | Space |
|---|---|---|
| Linear | O(n) | O(1) |
| Binary | O(log n) | O(1) |
| Jump | O(√n) | O(1) |
| Interpolation | O(log log n) average on evenly spread values, O(n) worst | O(1) |
n is the number of values. Interpolation Search is fast when values are evenly spread. When they are not, its performance can become O(n).
Example input and output
Input
- List: 1 3 5 7 9 11 13 15
- Target: 11
Output
- Binary: Found at position 6 in 2 comparisons.
- Linear: 6 comparisons.
- Jump: 4 comparisons.
Edge cases
- Target not found: Every algorithm finishes after checking all possible positions and reports that the value is not in the list.
- Duplicate values: Linear Search returns the first match. The other algorithms return one matching position.
- Target outside the range: If the target is smaller than the first value or larger than the last value, Interpolation Search can rule it out without checking a position.
- Unsorted list: The simulator sorts the list before Binary, Jump and Interpolation Search and informs you about it.
Where the code lives
- Enginesrc/lib/searching.ts
- Workspacesrc/components/SearchingDemo.tsx
- Checkstests/searching.test.ts