Binary search (Edexcel GCSE Computer Science): Quizzes
📚Quizzes
Practise the questions
12 questions from this quiz
ShowHide
Practise the questions
12 questions from this quiz
What is the critical requirement for binary search to work?
What is the critical requirement for binary search to work?
The list must be sorted
What strategy does binary search use?
What strategy does binary search use?
Divide-and-conquer
If the search item is smaller than the median, what do you discard?
If the search item is smaller than the median, what do you discard?
Median and everything to its right
If the search item is larger than the median, what do you discard?
If the search item is larger than the median, what do you discard?
Median and everything to its left
In a list of 13 items, which item is the median?
In a list of 13 items, which item is the median?
The 7th item
In a list of 10 items, which position is the median?
In a list of 10 items, which position is the median?
Position 5
What formula finds the median position in binary search?
What formula finds the median position in binary search?
When does binary search successfully terminate?
When does binary search successfully terminate?
When search item equals the median
What does each step of binary search eliminate?
What does each step of binary search eliminate?
Roughly half of remaining possibilities
For 1000 items, what's the maximum checks binary search needs?
For 1000 items, what's the maximum checks binary search needs?
10 checks
In the worked example, how many steps did it take to search 11 cards?
In the worked example, how many steps did it take to search 11 cards?
3 steps
Why is binary search more efficient than linear search?
Why is binary search more efficient than linear search?
Logarithmic time complexity