Binary Search: The Winning Strategy of the Up-Down Game

Chris is playing the "Up-Down Game" with a friend.

The goal is to guess the number the friend is thinking of, between 1 and 100.

Chris: "1?"

The friend gets annoyed. "Are you going to call out every number up to 100?"

This is the Linear Search we learned last time. You might actually have to ask 100 times.

A smart Chris would have asked like this:

Chris: "50!"

With just two questions, he reduced the candidates from 100 to 25. This is the magic of Binary Search.

1. Divide and Conquer: Split and Discard

Binary Search is a powerful algorithm that can only be used on "Sorted Data".

The core idea is to reduce the search range by half repeatedly.

2. Implementing in JavaScript

To implement Binary Search, you need 3 pointers (variables).

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  // If the left pointer crosses the right pointer, search ends (Not found)
  while (left <= right) {
    // Calculate middle index
    let mid = Math.floor((left + right) / 2);
    let currentElement = arr[mid];

    // 1. Found it!
    if (currentElement === target) {
      return mid;
    }
    
    // 2. Is the target smaller? -> Discard the Right (larger side)
    if (target < currentElement) {
      right = mid - 1;
    } 
    // 3. Is the target larger? -> Discard the Left (smaller side)
    else {
      left = mid + 1;
    }
  }

  return -1; // Never found
}

// CAUTION: The array MUST be sorted!
const sortedStates = ["Alabama", "Alaska", "Arizona", "Arkansas", "California", ...];
binarySearch(sortedStates, "California");

3. Performance Analysis: The Power of Log

The Time Complexity of Binary Search is O(log N).

How fast is that?

When Linear Search asks 4 billion questions, Binary Search only needs to ask 32 times. The difference is overwhelming.

4. The Fatal Constraint: Sorting

"Wow, then shouldn't we just use Binary Search for everything?"

Unfortunately, there is a prerequisite. The data must be sorted in order.

This is where the Sorting we learned in Chapter 2 shines.

If you invest the cost to sort the data once (O(N log N)), you can enjoy O(log N) search speeds forever after.

5. Key Takeaways

Now you have mastered how to search through linear data (Arrays).

But not all data in the world stands in a single line.

Folder structures, Organization charts, HTML DOM trees... How do we search through data that branches out like this (Tree/Graph)?

It's time to learn the two methods of exploring branching paths like a maze game: DFS (Depth-First Search) and BFS (Breadth-First Search).

🔗 References