Back to the full dot-point answer
SingaporeComputer ScienceQuick questions
Algorithms and Problem Solving
Quick questions on Linear and binary search explained: H2 Computing
6short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.
What is linear search?Show answer
Linear search checks each element in turn until it finds the target or runs out:
What is binary search?Show answer
Binary search needs a sorted list. It compares the target with the middle element and discards the half that cannot contain it:
What are off-by-one in the bounds?Show answer
After a comparison, move to mid + 1 or mid - 1, not mid, or the loop can spin forever on a two-element range.
What is q1?Show answer
State the worst-case complexity of linear search and explain when it occurs. [2 marks]
What is q2?Show answer
Why must a list be sorted for binary search to work? [2 marks]
What is q3?Show answer
Roughly how many comparisons does binary search need for a sorted list of 1024 items in the worst case? [1 mark]
Have a question we have not covered?
This dot-point answer is short enough that we have not extracted many short questions yet. Read the full dot-point answer or ask Mo, our study assistant, in the chat for follow ups.