Linear and binary search visualiser
Type a list and a value to find, then pick linear or binary search. Press Play to see which cell is checked next, how binary search throws away half the list each time, and how many comparisons each search needs.
How to use it
- 1Pick linear or binary search, type a list (in ascending order for binary search) and the value to find.
- 2Press Show me, then Play. The cell being checked is marked, and for binary search low, mid and high move.
- 3Read how many comparisons it took, and follow the Java line that is running.
The animation needs JavaScript. Every step is written out below.
Result
- Result
- found at position 3, 4 comparisons
Every step in words (6 steps)
- Looking for 4. pos = -1 means 'not found yet'.
- Is a[0] == key? 9 == 4 is false.
- Is a[1] == key? 3 == 4 is false.
- Is a[2] == key? 7 == 4 is false.
- Is a[3] == key? 4 == 4 is true.
- Found 4 at position 3 (after 4 comparisons).
About the Linear and binary search visualiser
What it does
Looks for a value in your list with a linear or a binary search and shows each comparison. For binary search it shows low, mid and high, and greys out the half of the list that has been thrown away. The result says whether the value was found, at which position, and how many comparisons were needed.
Linear and binary search
- Linear search: checks the cells one after another from the start. It works on any list.
- Binary search: needs the list in ascending order. It checks the middle cell and throws away the half that cannot contain the value, so a list of 15 values needs at most 4 comparisons.
Positions start from 0
The cells are numbered from 0, as Java array indexes are, so the first value is at position 0.
Common questions
Why does binary search need a sorted list?
Because each step decides which half to keep by asking whether the value in the middle is smaller or bigger than the one you want. That only tells you where to look if the list is in order.
How many comparisons does binary search need?
At most ⌊log2 n⌋ + 1: 3 for 4 to 7 values and 4 for 8 to 15 values, compared with up to n for a linear search.
What does the search return when the value is not there?
Both searches report -1 (or ‘not found’): a linear search after checking every cell, a binary search when low becomes greater than high.
Can I see the code in Python, JavaScript or C++?
Yes. Choose the language in the menu above the code. Only the listing changes: the steps are always worked out from the Java program that ISC uses, and the highlighted line moves to the matching line of the language you chose.
Practise on real ISC questions
More Computer Science tools
- Boolean algebra solverSimplify any expression: the laws step by step, truth table, K-map and the logic circuit.
- Infix to postfix converterInfix to postfix or prefix with the stack table, and postfix evaluation step by step.
- Binary tree and BST toolBuild a binary search tree, rebuild a tree from two traversals, and get every traversal and fact.
- Stack and queue simulatorRun push, pop, insert and delete on a stack, queue, circular queue or dequeue, and watch the pointers move.
- Recursion visualiserWatch factorial, Fibonacci, power, GCD and sum of digits run: the calls, the call stack and the returns.
- Tower of Hanoi visualiserWatch the discs move between the pegs while the recursive calls and the call stack build up.
- Binary search tree visualiserWatch values being inserted into a binary search tree, searched for, and walked inorder, preorder and postorder.
- Binary tree traversal visualiserClick a binary tree together and watch preorder, inorder and postorder walk it, with the recursive calls on the call stack.
- Stack and queue visualiserWatch push, pop, insert and delete move top, front and rear along the array, with overflow and underflow.
- Linked list visualiserWatch nodes being added, deleted, searched, traversed and reversed, with start, p, prev and curr moving along the arrows.
- 2D array visualiserWatch row-wise, column-wise, diagonal, boundary and spiral walks number the cells of a 2D array in the order they print.
- Sorting visualiserWatch bubble, selection and insertion sort compare, swap and shift your own list, step by step.