Lesson 02

Linear vs. Binary Search

Understanding how we find items in a sorted list and why algorithm design drastically impacts execution speed.

The Searching Problem

Imagine looking up a word in a physical dictionary or searching for a contact in your phone. How you search determines whether it takes 2 seconds or 20 minutes. In computer science, Linear Search and Binary Search represent the two fundamental strategies.

Linear Search O(n) - Sequential

Checks items one by one from left to right until the target is found or the array ends. Works on unsorted or sorted data.

Key Characteristics:

• Checks elements sequentially.
• No sorted array required.
• Slow for large datasets (1,000 items = up to 1,000 checks).

Binary Search O(log n) - Divide & Conquer

Repeatedly cuts the sorted array in half by comparing the middle element to the target value.

Key Characteristics:

• Requires array to be sorted beforehand.
• Eliminates half the remaining elements with every step.
• Extremely fast for large datasets (1,000 items = ~10 checks max).

Why Scale Matters: Speed Comparison

Here is how the maximum number of steps compares as your dataset grows: