IB Computer Science Topic B2.4.2: Constructing and Tracing Algorithms for Linear and Binary Search Notes

Linear and Binary Search: Two Ways to Find an Item

1. Linear search checks every element in turn until it finds the target or runs out of elements.
2. Binary search repeatedly halves a sorted list, discarding the half that cannot contain the target.
3. Linear search works on any list; binary search buys its speed with the requirement that the data is already in order.

Linear Search: Check Every Element in Turn

1. Initialize a variable foundIndex to -1, to record that the target has not been found yet.
2. Iterate through the list from index 0 to the last index.
3. If the current element matches the target, set foundIndex to the current index and stop the loop.
4. Return foundIndex, which is still -1 if the loop finished without a match.

Tracing Linear Search on [5, 3, 8, 4, 2]

Searching for 8 takes three comparisons and returns index 2.

1. Searching for 7 is the worst case: all five elements are compared and the algorithm returns -1.
2. The number of comparisons is at most the number of elements, which is why linear search is O(n).

Binary Search: Halve the Range Each Pass

1. Precondition: the list must be sorted, or the algorithm discards the wrong half and misses the target.
2. Set left to the first index and right to the last index.
3. While left is less than or equal to right, calculate the midpoint as (left + right) integer-divided by 2.
4. If the midpoint value equals the target, return the midpoint index.
5. If the midpoint value is less than the target, the target must lie above it, so set left to mid + 1.
6. If the midpoint value is greater than the target, the target must lie below it, so set right to mid - 1.
7. If left passes right, the range is empty and the target is not present, so return -1.

Tracing Binary Search on a 13-Item List

1. The list is [10, 11, 12, 15, 20, 25, 45, 84, 129, 139, 483, 586, 685], with indices 0 to 12.
2. Searching for 139 finds it in two comparisons, where linear search would have taken ten.

Searching for 100 is the worst case, and the loop ends when left passes right.

1. Four passes searched thirteen items, because each pass throws away about half of what is left.
2. Doubling the list adds one pass, not double the work, which is what O(log n) means.

Comparing the Two: Efficiency Against Preconditions

1. On a million sorted items, the worst case is 1,000,000 comparisons against 20, because 2²⁰ is just over a million.
2. That gap only pays off if the data is already sorted, since sorting first costs O(n log n).
3. For a single search of unsorted data, linear search wins outright.
4. For repeated searches of the same data, sorting once and then using binary search wins.

Choosing a Search: Ask What the Data Is Doing

1. Ask whether the data is already sorted, and if not, how often it changes.
2. Ask how many searches will run against it, because sorting is a one-off cost spread across every later search.
3. Ask how large the data set is, since on twenty items the difference is invisible and on twenty million it decides whether the feature works.