DSA Day 60: Binary Search (The Dictionary Method)

📅 Date: April 4, 2026

🧠 Mood: The Sniper 🎯

🔥 Topic: DSA Day 60: Binary Search (The Dictionary Method)

💀 Why Did We Spend Weeks Sorting Data?

If you look at my recent posts, I spent a massive amount of time dissecting sorting algorithms. From the sluggish Bubble Sort to the highly optimized Quick Sort, I spent days just figuring out how to arrange numbers in ascending order. To be completely honest, a part of me felt lazy and burnt out recently. I took a few days off because I kept asking myself: "Why does sorting even matter so much?"

Today, the laziness vanished because the puzzle finally clicked. You don't sort data just to make it look pretty. You sort data so you can search through it at lightning speed.

Imagine looking for a specific word in an English dictionary. If the dictionary was completely unorganized (unsorted), you would have to read every single page from start to finish to find your word. In computer science, this is called Linear Search, and it operates at an abysmal $O(N)$ time complexity. But because the dictionary is alphabetically sorted, you can use the ultimate search algorithm: Binary Search.

---

📖 The Dictionary Method

Binary search works exactly how humans look for words in a dictionary. Let's say I am looking for the word "Recursion". I don't start at page one. I open the book exactly in the middle.

1. The Middle Man

I open the middle of the dictionary and find the letter 'M'. I instantly know that 'R' comes after 'M'. In that single split second, I have completely eliminated the entire first half of the dictionary. I don't even need to look at it. I have reduced my problem size by 50% in one move.

2. Repeat and Conquer

Now, I take the remaining right half of the dictionary and open it in the middle again. Maybe I land on 'T'. Since 'R' comes before 'T', I eliminate the right half this time. I keep slicing the remaining pages in half until I land exactly on "Recursion".

Because we are destroying half of the search space with every single check, the time complexity plummets to $O(\log N)$. To put that into perspective: If you have an array of 1,000,000 (one million) sorted items, Linear Search might take 1 million checks. Binary Search will find the item in a maximum of 20 checks. That is the power of algorithms.

---

💻 The C++ Code (Iterative Approach)

Writing Binary Search requires three pointers: a start pointer, an end pointer, and a mid pointer. Here is the cleanest way to implement it using a while loop.

#include <iostream>
#include <vector>
using namespace std;

// Function returns the index of target if found, else returns -1
int binarySearch(vector<int>& arr, int target) {
    int start = 0;
    int end = arr.size() - 1;

    // Keep searching while the search space is valid
    while (start <= end) {
        
        // Calculate mid. We use this formula to avoid integer overflow
        int mid = start + (end - start) / 2;

        // Condition 1: Target is found exactly at the middle!
        if (arr[mid] == target) {
            return mid; 
        }

        // Condition 2: Target is greater, ignore the left half
        if (arr[mid] < target) {
            start = mid + 1;
        }
        
        // Condition 3: Target is smaller, ignore the right half
        else {
            end = mid - 1;
        }
    }

    // If we exit the loop, the target does not exist in the array
    return -1;
}

int main() {
    // WARNING: The array MUST be sorted for Binary Search to work!
    vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    int target = 17;
    
    int resultIndex = binarySearch(primes, target);
    
    if(resultIndex != -1) {
        cout << "Target found at index: " << resultIndex;
    } else {
        cout << "Target not found in the array.";
    }
    return 0;
}

---

🎯 The Golden Rule

Never forget the golden rule: If the array is not sorted, Binary Search will fail completely. Tomorrow, I am going to look at some twisted interview questions where the array is rotated, making standard Binary Search fail, and how we have to modify the algorithm to fix it.