Linear Search vs Binary Search

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 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 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.