Linear and binary search
Practice Flashcards
Flip to reveal answersHow does linear search work, and what does it cost?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 5 Flashcards — Linear and binary search
Sign up free to track progress and get spaced-repetition review schedules.
Question
How does linear search work, and what does it cost?
Answer
It checks each item in turn until it finds the target or runs out, returning the position or -1. Best case O(1) if the target is first, worst case O(n) if it is last or absent.
Question
How does binary search work?
Answer
Look at the middle item. If it equals the target, stop. If it is too small the target is to the right, so move low to mid + 1; if too big, move high to mid - 1. Each step discards about half the remaining list.
Question
Why must binary search have sorted data?
Answer
Discarding half depends on knowing which half the target would be in, which only holds if the list is in order. On unsorted data it does not run slowly — it returns the wrong answer.
Question
How does binary search terminate?
Answer
When low passes high, meaning there is nothing left to search. It then returns -1 to indicate the target is absent.
Question
How do the two searches grow with the data?
Answer
Doubling the list doubles linear search's worst case, but adds only one comparison to binary search's. Sixteen items need at most four binary comparisons; a million need about twenty.
Read the notes
Full study notes for Linear and binary search
Topic 6.4 hub
Programming algorithms
More from Topic 6.4
All flashcards in this topic
Computer Science exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free