Linear vs binary search
Linear vs binary search is an interactive experiment in Algorithms Visualised, a free simulation from StudyFi Lab that runs right in your browser.
Linear search checks the elements one by one, so in the worst case it needs n steps — O(n). Binary search only works on a sorted array: it looks at the middle and, depending on the result, throws away a whole half. After each step at most half is left, so it needs at most ⌈log₂(n+1)⌉ steps — O(log n). For 40 elements that is 6 steps instead of 40.
Try this: Set 40 elements and search for the last value. Then pick a number that is not in the array — how many steps does each search need to find out?
Frequently asked questions
What does the “Linear vs binary search” experiment show?
Linear search checks the elements one by one, so in the worst case it needs n steps — O(n). Binary search only works on a sorted array: it looks at the middle and, depending on the result, throws away a whole half. After each step at most half is left, so it needs at most ⌈log₂(n+1)⌉ steps — O(log n). For 40 elements that is 6 steps instead of 40.
How do I try “Linear vs binary search”?
Set 40 elements and search for the last value. Then pick a number that is not in the array — how many steps does each search need to find out?
Studying for a test?
Upload your notes and StudyFi turns them into flashcards, tests and podcasts.