Binary Seach

Imagine you’re searching for a word in a dictionary.
You don’t start from page 1, right?
You open somewhere in the middle.

• If your word comes before → go left

• If it comes after → go right

This is exactly how Binary Search works.

---

Core Idea of Binary Search

Instead of checking every element (like linear search), we:

• Pick the middle element

• Compare with target

• Eliminate half of the search space

---

Basic Binary Search Formula

mid = (Left + right) / 2

Decision Making

Once we calculate mid, we compare:

• If arr[mid] == target
  → Target found

• If arr[mid] > target
  → Target lies on the left side
  → Move:

  right = mid - 1;
  

• If arr[mid] < target

  → Target lies on the right side

  → Move:

  left = mid + 1;
  

---

Problem Statement:

Given a sorted array of size n and an integer target, determine whether the target exists in the array.

If the target is present, return its index (0-based).
If the target is not present, return -1.

---

Step-by-Step Dry Run

Let’s say you have an array:

[3, 5, 2, 1, 4]
 0  1  2  3  4

First rule:

Binary Search only works on a sorted array

So we sort it:

[1, 2, 3, 4, 5]
 0  1  2  3  4

Now Search Target = 4

Step 1:

[1, 2, 3, 4, 5]
 0  1  2  3  4
 l     m     r
           

• mid = 2 → value = 3

• 4 > 3 → ignore left half

• Move right: l = 3

Step 2:

[1, 2, 3, 4, 5]
 0  1  2  3  4
          m  r
          l

• mid = 3 → value = 4

• Found!

---

Code

int l = 0, r = n - 1;

while (l <= r) {
    int mid = (l + r) / 2;

    if (arr[mid] == target) {
        return mid; // found
    } else if (arr[mid] < target) {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

return -1; // not found

---

Complexity

• Time Complexity: O(log n)

• Space Complexity: O(1)

---

Where This Pattern is Used

This is where things get interesting 👇

The same binary search logic helps solve multiple problems:

1. First & Last Occurrence

2. Frequency of an Element

3. Count of Elements Greater Than X

4. Count of Elements Between X and Y

Once you understand pointer movement, all these problems become easy.