Linear Search vs Binary Search
You'll learn to
- -Implement linear search and explain why it is O(n) regardless of sortedness
- -Implement binary search and explain why it requires sorted input
- -Trace binary search's left/mid/right pointer movement across an example
Searching for a value is among the most common operations any program performs, and this module builds the two foundational approaches before the next chapter hardens the second one against messier real-world input for Level 6.
Linear Search: Works Anywhere, Costs O(n)
Linear search works on sorted or unsorted data equally well, since it makes no assumption about ordering at all - but that generality is exactly why it can never do better than O(n): in the worst case, a missing target or one sitting at the very last position forces every element to be checked.
Binary Search: O(log n), But Only On Sorted Data
Binary search exploits sortedness directly. It tracks a left and right boundary, computes the midpoint between them, and compares the middle element to the target: if they match, the search is done; if the target is larger, the entire left half (including mid) can be discarded, since sortedness guarantees nothing smaller than mid could be a match; if the target is smaller, the entire right half is discarded instead. Each comparison throws away half of whatever search space remained.
Tracing it on items = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] searching for 23: left = 0, right = 9, mid = 4, items[4] = 16 is less than 23, so left becomes 5. Next, mid = (5 + 9) // 2 = 7, items[7] = 56 is greater than 23, so right becomes 6. Next, mid = (5 + 6) // 2 = 5, items[5] = 23 matches the target, and the function returns index 5 - three comparisons total, instead of scanning up to all ten elements.
Binary search's O(log n) guarantee evaporates completely on unsorted input - there is no shortcut around sorting first (or maintaining sorted order as data arrives). Sorting itself costs O(n log n) at best, covered in a later tier, so binary search pays off most when the same sorted data is searched many times over.
When would you reach for binary search instead of a simple loop?
"Whenever I need to search for something in a list."
"Whenever the data is already sorted, or I can afford to sort it once and then search it many times - binary search turns an O(n) scan into an O(log n) one, and the more searches performed against the same sorted data, the more that upfront sort pays for itself."