Loading...
Linear search checks items in sequence and can work with unsorted data. Binary search compares a target with the middle of a sorted search range, then discards the half that cannot contain it. Repeat until found or the range is empty. Without sorted data, the discard step is unjustified. Distinguish an index from the value stored at that index and state whether the example uses zero-based indexing.
Video by Craig'n'Dave. The video’s own board label is retained; follow the specification reference and scope notes on this lesson for assessed content.
Viewing focus: Trace linear and binary search
After watching, attempt these questions before opening the answers. You can also use the written lesson below.
After watching 1: What is required for ordinary binary search?
Sorted data. Its half-discard logic depends on order.
After watching 2: Which method compares adjacent items repeatedly?
Bubble sort. Out-of-order neighbours are swapped.
What you'll be able to do
Linear search checks items in sequence and can work with unsorted data. Binary search compares a target with the middle of a sorted search range, then discards the half that cannot contain it. Repeat until found or the range is empty. Without sorted data, the discard step is unjustified. Distinguish an index from the value stored at that index and state whether the example uses zero-based indexing.
Bubble sort compares adjacent items and swaps out-of-order pairs. Repeated passes move large values toward the end in ascending order. Insertion sort takes an item and places it into the correct position within an already sorted prefix. Merge sort splits a list, sorts the parts and merges them in order. A merge step repeatedly compares the front remaining items; it does not simply concatenate the two lists.
Binary search can use far fewer comparisons than linear search on a large sorted list, but sorting or maintaining that list has a cost. Bubble sort is simple but often inefficient for large inputs; merge sort uses extra storage in its common implementation. An already nearly sorted list can favour insertion sort. Use the board’s required algorithms and the given data rather than asserting that one method is always best for every size, structure and update pattern.
Attempt these problems on paper before opening the worked reasoning. Explain your steps as well as giving a final answer.
Common mistakes to avoid
Key takeaways
Question 1: Perform one left-to-right bubble pass on [4, 1, 3, 2].
[1, 3, 2, 4].
Check the assessed scope and practical or mathematical requirements.
An external explanation or interactive activity to use alongside the lesson. It may include extension material.
Close the notes and answer from memory. Revisit any explanation you cannot yet reconstruct.
Test yourself
Answer a few questions, then review anything you missed.
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.