Search Algorithms Visualization

The Art of Finding Data

How do computers find a needle in a haystack? Does sorting the haystack help?

The Short Answer

help How do you find a number?

In a standard (unsorted) list, you must check every single number one by one until you find a match. This is called Linear Search.

bolt Does sorting help?

Yes, immensely. If the list is sorted, you can eliminate half the remaining numbers with every single guess. This is called Binary Search.

manage_search

1. Linear Search (Unsorted)

Imagine a shuffled deck of cards. To find the Queen of Hearts, you have to turn over the top card, check it, then the next, and so on. You might find it instantly (Best Case), or it might be the very last card (Worst Case).

2
5
12
59
2
52
86
40
26
17
40
74
99
22
79
New numbers generated. Steps: 0
filter_list

2. Binary Search (Sorted)

Now imagine a phone book (which is sorted alphabetically). To find "Smith", you open the book to the middle. If you see "M", you know "S" is in the second half. You ignore the entire first half. You repeat this split until you find the name.

1
3
4
9
12
14
22
22
40
47
68
69
73
96
97
New sorted numbers generated. Steps: 0
functions

3. Complexity Analysis

Time Complexity Growth

Steps (Time)
Elements (N)
O(n) Linear
O(log n) Binary

Note: Graph is illustrative. Logarithmic growth is significantly flatter than linear.

Algorithm Big O (Time) Input Requirement
Linear Search O(n) None (Any Array)
Binary Search O(log n) Must be Sorted

Real World Example:

If you have 1,000,000 items:

  • Linear: Up to 1,000,000 checks.
  • Binary: Only ~20 checks!
code

Code Implementation

Python 
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1  # Not found
JavaScript 
function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    let guess = arr[mid];

    if (guess === target) return mid;
    if (guess > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1; // Not found
}