Searching Algorithms
Run linear, binary, ternary and quaternary search on your own array and step through the code one line at a time.
Setup
Pick an algorithm, then type the array and the value to find.
Binary search for 52
Search for 52 in 13 values.
Python Implementation
The highlighted line runs next.
Variables
| target | 52 |
| low | 0 |
| high | 12 |
Step count vs. step cost
Splitting into more parts means fewer rounds, but each round needs more comparisons. That is why binary search is usually the sweet spot.
| Algorithm | Needs sorted data | Comparisons per round | Time | Split points |
|---|---|---|---|---|
| Linear | No | 1 (one item each step) | O(n) | check a[0], a[1], ... in order |
| Binary | Yes | 1 | O(log₂ n) | mid = (low + high) // 2 |
| Ternary | Yes | up to 2 | O(log₃ n) | m1 = low + (high − low) // 3, m2 = high − (high − low) // 3 |
| Quaternary | Yes | up to 3 | O(log₄ n) | qk = low + k·(high − low) // 4, k = 1, 2, 3 |
Lower bound
Any comparison-based search of sorted data needs Ω(log n) comparisons in the worst case.
Boundary search
Binary search also finds boundaries: the first value ≥ x, an insertion point, or the first “true” of a condition.
Feedback
Each comparison with the target says which part of the array can be thrown away.
Problem: the first open slot at or after 14:00
Slots are sorted: 09:00, 10:30, 12:00, 14:00, 14:00, 15:30. An exact search may land on either 14:00. A lower-bound search finds the first one: if a[mid] is earlier than 14:00, move low right; otherwise keep mid as a candidate and move high left.
About This Simulation
This searching simulator runs linear, binary, ternary and quaternary search on your own array and steps through the Python code one line at a time, showing the variables and the part of the array still being searched.
Features
- Linear, binary, ternary and quaternary search
- Your own array and target, or a random one
- Line-by-line code execution with the current line highlighted
- Live variables (low, high, mid and split points) and comparison count
- Discarded parts of the array faded out after each step
Topics covered
- Linear Search
- Binary Search
- Ternary Search
- Quaternary Search
- Divide and Conquer
- Time Complexity O(log n)
Explanation
A search algorithm finds the position of a target value in a list. Linear search checks every element in turn and works on any list. Binary, ternary and quaternary search need a sorted list: they compare the target with one, two or three split points and throw away every part that cannot contain it.
How it works
- Linear search: compare a[0], a[1], a[2], ... with the target until it is found or the list ends.
- Binary search: set low = 0 and high = n − 1, compute mid = (low + high) // 2, and compare a[mid] with the target.
- If a[mid] equals the target, stop. If the target is smaller, search the left half (high = mid − 1); otherwise search the right half (low = mid + 1).
- Ternary and quaternary search split the range into three or four parts using two or three split points, and keep only the part that can contain the target.
- If low becomes greater than high, the target is not in the array.
Why it matters
Searching is everywhere: databases, dictionaries, autocomplete and the standard libraries of every language. Binary search is also used to find boundaries (the first value ≥ x, insertion points) and to search over answers in competitive programming. It is a core topic of CSE221.
Frequently Asked Questions
What is the time complexity of binary search?
O(log n) in the worst and average case, because each comparison halves the remaining range. The best case is O(1) when the middle element is the target.
Why does binary search need a sorted array?
Binary search decides which half to discard by comparing the target with the middle element. That only works if every element on the left is smaller and every element on the right is larger.
Is ternary search faster than binary search?
No. Ternary search needs fewer rounds (log₃ n instead of log₂ n) but up to two comparisons per round, so it makes more comparisons overall. Binary search is the most efficient comparison-based search on a sorted array.
When should I use linear search?
Use linear search for unsorted data, very small lists, or when you only search once (sorting first would cost O(n log n)). Its time complexity is O(n).
Related Simulations
Algorithms
Sorting Algorithm Visualiser
Visualise sorting algorithms
Algorithms
A* Algorithm
Show pathfinding using cost, heuristic, and total estimated distance.
Algorithms
BFS (Breadth First Search) Simulator
Build interactive graphs and watch BFS explore networks level-by-level using a visual queue.
Algorithms
DFS (Depth First Search) Simulator
Build interactive graphs and watch DFS plunge down deep paths and backtrack using a visual stack.