What's covered
Key facts
Binary search starts by checking the middle item of the list.
Bubble sort works on a list of any size.
A sorted phone book is the classic case where binary search beats linear by a large margin.
Arrows (flowlines) join the shapes and show the direction the algorithm moves through them.
Linear search finds the item fastest when the target is at (or near) the start of the list.
Common pseudocode forms for assigning a value are SET x TO 5 or x ← 5.
Trace a snippet by updating the variable column at each step: starting x = 0, after SET x TO x+5 then SET x TO x*2, x ends at 10.
On a large sorted list, binary search is much faster than linear search.
At each step bubble sort compares two adjacent items.
On large sorted data, binary search is much faster than linear search.
Sample questions
A taste of the 73 questions in this topic — answers marked. Sign up to practise the full set with spaced repetition.
Which item does binary search look at first?
- •A random item
- •The first item
- •The last item
- ✓The middle item
How does bubble sort sort a list?
- •Finds the smallest item and moves it first
- •Inserts each item into its correct position
- •Splits the list in half each pass
- ✓Swaps neighbouring pairs repeatedly
Why compare two algorithms solving the same problem?
- ✓One may be more efficient
- •To check they produce the same code
- •To decide which programmer wrote better comments
- •To find which one uses more variables
Which shape represents a decision in a flowchart?
- ✓Diamond shape
- •Oval shape
- •Parallelogram shape
- •Rectangle shape
How does a linear search work?
- ✓Checks each item one by one until the target is found
- •Hashes the target value to compute the index of the item directly
- •Repeatedly halves the list, checking only the middle item each time
- •Sorts the list first, then jumps to the position where the target should be
Why use pseudocode?
- •Convert binary to decimal numbers
- ✓Plan an algorithm in plain language
- •Run the algorithm on the CPU directly
- •Send the algorithm over the network
Try it for four weeks. Free.
One school. Unlimited classes. No card limit. No teacher limit. If your students aren't practising daily by the end of the trial, you owe us nothing.