55. Binary Search

🔗 LeetCode Problem: 704. Binary Search
📊 Difficulty: Easy
🏷️ Topics: Array, Binary Search

Problem Statement

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints: - 1 <= nums.length <= 10^4 - -10^4 < nums[i], target < 10^4 - All the integers in nums are unique - nums is sorted in ascending order

🎨 Visual Understanding

The Problem Visualized

nums = [-1, 0, 3, 5, 9, 12], target = 9

Array: [-1, 0, 3, 5, 9, 12]
Index:  0   1  2  3  4   5
                      ↑
                   Found at index 4!

nums = [-1, 0, 3, 5, 9, 12], target = 2

Array: [-1, 0, 3, 5, 9, 12]
Index:  0   1  2  3  4   5
            ↑  ↑
       0 < 2 < 3

Target 2 is not in array
Return: -1

🚨 CRITICAL INSIGHT - Why Binary Search Works

THE Most Fundamental Algorithm!

Binary Search is THE classic divide-and-conquer algorithm!

Key Requirements:
  1. Array must be SORTED ✓
  2. Need to find EXACT element
  3. Can eliminate HALF at each step
  4. Need O(log n) time

The Magic:
  At each step, compare target with middle element
  Based on comparison, eliminate half of search space

  If target = mid: Found it!
  If target < mid: Must be in left half
  If target > mid: Must be in right half

Example: Find 9 in [-1, 0, 3, 5, 9, 12]

Step 1: Check middle (index 2, value 3)
  [-1, 0, 3, 5, 9, 12]
          ↑
        mid = 3
  9 > 3, so search right half [5, 9, 12]

Step 2: Check middle (index 4, value 9)
  [5, 9, 12]
      ↑
    mid = 9
  9 == 9, FOUND at index 4! ✓

Only 2 comparisons instead of 5!

Why O(log n)?

Search Space Reduction:
  Start: n elements
  After 1 comparison: n/2 elements
  After 2 comparisons: n/4 elements
  After 3 comparisons: n/8 elements
  ...
  After k comparisons: n/(2^k) elements

When does it become 1?
  n/(2^k) = 1
  n = 2^k
  k = log₂(n)

So maximum comparisons = log₂(n)

Example:
  n = 1,000,000 (1 million elements)
  Linear search: 1,000,000 comparisons worst case
  Binary search: log₂(1,000,000) ≈ 20 comparisons worst case

  1,000,000 vs 20! That's the power of binary search!

The Binary Search Invariant

Loop Invariant:
  If target exists in array, it must be in range [left, right]

How it works:
  Initially: left = 0, right = n-1
    Target could be anywhere in [0, n-1]

  After each comparison at mid:
    If target < nums[mid]:
      Target must be in [left, mid-1]
      Update: right = mid - 1

    If target > nums[mid]:
      Target must be in [mid+1, right]
      Update: left = mid + 1

    If target == nums[mid]:
      Found it! Return mid

When left > right:
  Search space is empty
  Target doesn't exist
  Return -1

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Core Logic:

Check each element one by one:
  If element equals target, return its index
  If we reach the end, return -1

Implementation

public int search(int[] nums, int target) {
    // Check each element
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;  // Found
        }
    }
    return -1;  // Not found
}

⏰ Time: O(n) - Check every element
💾 Space: O(1) - Only variables

Why This Works:

Simple: compare target with each element
If match found, return index
If loop ends, target not in array

❌ Problem: Doesn't meet O(log n) requirement! Doesn't use sorted property!

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

🧠 The Core Insight

Array is SORTED → Binary Search is perfect!

Key Idea:
  Compare target with middle element
  Eliminate half the array based on comparison
  Repeat until found or search space empty

This is THE classic binary search template!

The Strategy:

Standard Binary Search Algorithm:

1. Set left = 0, right = n-1
2. While left <= right:
   a. Calculate mid = left + (right - left) / 2
   b. If nums[mid] == target: return mid
   c. If nums[mid] < target: left = mid + 1 (search right)
   d. If nums[mid] > target: right = mid - 1 (search left)
3. Return -1 (not found)

Implementation

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        // Calculate mid safely (avoids overflow)
        int mid = left + (right - left) / 2;

        // Check if target is at mid
        if (nums[mid] == target) {
            return mid;  // Found!
        }

        // If target is greater, ignore left half
        if (nums[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }

    // Target not found
    return -1;
}

⏰ Time: O(log n) - Binary search
💾 Space: O(1) - Only pointers

🔍 Dry Run

Example 1: nums = [-1, 0, 3, 5, 9, 12], target = 9

Initial: left = 0, right = 5
         [-1, 0, 3, 5, 9, 12]
          ↑                ↑
        left             right

Iteration 1:
  mid = 0 + (5 - 0) / 2 = 2
  nums[2] = 3
  3 < 9, search right half
  left = 3
  [-1, 0, 3, 5, 9, 12]
                ↑     ↑
              left  right

Iteration 2:
  mid = 3 + (5 - 3) / 2 = 4
  nums[4] = 9
  9 == 9, FOUND!
  return 4 ✓

Total comparisons: 2

Example 2: nums = [-1, 0, 3, 5, 9, 12], target = 2

Initial: left = 0, right = 5
         [-1, 0, 3, 5, 9, 12]
          ↑                ↑
        left             right

Iteration 1:
  mid = 0 + (5 - 0) / 2 = 2
  nums[2] = 3
  3 > 2, search left half
  right = 1
  [-1, 0, 3, 5, 9, 12]
   ↑   ↑
  left right

Iteration 2:
  mid = 0 + (1 - 0) / 2 = 0
  nums[0] = -1
  -1 < 2, search right half
  left = 1
  [-1, 0, 3, 5, 9, 12]
       ↑
    left/right

Iteration 3:
  mid = 1 + (1 - 1) / 2 = 1
  nums[1] = 0
  0 < 2, search right half
  left = 2
  [-1, 0, 3, 5, 9, 12]
          ↑
        left (left > right)

Loop ends (left > right)
return -1 ✓

Total comparisons: 3

Example 3: nums = [5], target = 5

Initial: left = 0, right = 0
         [5]
          ↑
       left/right

Iteration 1:
  mid = 0 + (0 - 0) / 2 = 0
  nums[0] = 5
  5 == 5, FOUND!
  return 0 ✓

Total comparisons: 1

Example 4: nums = [5], target = -5

Initial: left = 0, right = 0
         [5]
          ↑
       left/right

Iteration 1:
  mid = 0 + (0 - 0) / 2 = 0
  nums[0] = 5
  5 > -5, search left half
  right = -1
  [5]
  (left > right)

Loop ends (left > right)
return -1 ✓

🎯 Why This Works - Deep Dive

The Loop Condition: while (left <= right)
═══════════════════════════════════════════════════════════════

Why left <= right and not left < right?
  We need to check the case when left == right
  This is when search space has exactly 1 element

Example: [5], target = 5
  left = 0, right = 0
  Need to check nums[0]
  So loop must run when left == right

The Mid Calculation: left + (right - left) / 2
═══════════════════════════════════════════════════════════════

Why not (left + right) / 2?
  When left + right > Integer.MAX_VALUE: OVERFLOW!

Example:
  left = 2,000,000,000
  right = 2,000,000,000
  left + right = 4,000,000,000 > 2^31 - 1
  Integer overflow! Wrong result!

Safe calculation:
  left + (right - left) / 2
  = left + (2,000,000,000 - 2,000,000,000) / 2
  = left + 0
  = 2,000,000,000 ✓

Always safe, no overflow!

The Pointer Updates: Always ±1
═══════════════════════════════════════════════════════════════

Why left = mid + 1 and right = mid - 1?
  We've already checked mid
  mid is not the target
  So eliminate mid from search space

If we use left = mid or right = mid:
  Infinite loop risk!

Example of infinite loop:
  nums = [1, 3], target = 3
  left = 0, right = 1
  mid = 0, nums[0] = 1 < 3
  If left = mid = 0: No progress! Infinite loop!

With left = mid + 1 = 1: Progress! ✓

Loop Termination:
═══════════════════════════════════════════════════════════════

When does loop end?
  When left > right

What does this mean?
  Search space is empty: [right, left]
  We've checked all elements
  Target doesn't exist
  Return -1

This is guaranteed to happen:
  Search space shrinks by at least 1 each iteration
  Eventually left > right
  No infinite loops!

The Classic Binary Search Template

This is THE standard template for binary search:

┌─────────────────────────────────────────────────────────────┐
│ CLASSIC BINARY SEARCH TEMPLATE                              │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│ int left = 0, right = n - 1;                               │
│                                                             │
│ while (left <= right) {                                    │
│     int mid = left + (right - left) / 2;                   │
│                                                             │
│     if (nums[mid] == target) return mid;                   │
│                                                             │
│     if (nums[mid] < target) {                              │
│         left = mid + 1;                                    │
│     } else {                                               │
│         right = mid - 1;                                   │
│     }                                                       │
│ }                                                           │
│                                                             │
│ return -1;                                                  │
│                                                             │
└─────────────────────────────────────────────────────────────┘

Memorize this! Base for all binary search problems!

⚠️ Common Mistakes to Avoid

Mistake 1: Overflow in mid calculation

// ❌ WRONG - Can overflow
int mid = (left + right) / 2;

// ✓ CORRECT - Safe from overflow
int mid = left + (right - left) / 2;

Mistake 2: Wrong loop condition

// ❌ WRONG - Misses single element case
while (left < right) {
    // ...
}

// ✓ CORRECT - Checks single element
while (left <= right) {
    // ...
}

Mistake 3: Not using ±1

// ❌ WRONG - Can cause infinite loop
if (nums[mid] < target) {
    left = mid;  // Infinite loop risk!
}

// ✓ CORRECT - Always make progress
if (nums[mid] < target) {
    left = mid + 1;
}

Mistake 4: Wrong initialization

// ❌ WRONG
int right = nums.length;  // Out of bounds!

// ✓ CORRECT
int right = nums.length - 1;  // Last valid index

Mistake 5: Returning wrong value

// ❌ WRONG
return left;  // Should return -1 when not found

// ✓ CORRECT
return -1;  // Not found

🎯 Pattern Recognition

Problem Type: Binary Search - Classic/Exact Match
Core Pattern: Divide and Conquer Search

When to Apply:
✓ Array is SORTED
✓ Need to find EXACT element
✓ Need O(log n) time
✓ All elements unique or distinct
✓ Simple equality check

Recognition Keywords:
- "Sorted array"
- "Find target"
- "Return index or -1"
- "O(log n) runtime"
- "Ascending/descending order"

Similar Problems:
- Search Insert Position (LC 35)
- First Bad Version (LC 278)
- Find First and Last Position (LC 34)
- Search in Rotated Sorted Array (LC 33)
- Sqrt(x) (LC 69)

This is THE BASE problem:
┌────────────────────────────────────────────┐
│ This is THE most fundamental BS problem!   │
│                                            │
│ All other BS problems are variations of:  │
│   - This classic template                  │
│   - Modified search conditions             │
│   - Different return values                │
│   - Additional constraints                 │
│                                            │
│ Master this first!                         │
└────────────────────────────────────────────┘

Learn this template by heart!

🧠 Interview Strategy

Step 1: "Array is sorted, need O(log n) → Binary Search"
Step 2: "Use classic binary search template"
Step 3: "left = 0, right = n-1, loop while left <= right"
Step 4: "Compare target with mid, eliminate half"
Step 5: "Return mid if found, -1 if not found"

Key Points to Mention:
- Recognize sorted array → binary search
- Classic template: left <= right
- Safe mid: left + (right - left) / 2
- Three cases: equal, less, greater
- Always use mid ± 1
- Return -1 when not found
- Time: O(log n), Space: O(1)
- Search space halves each iteration

Why This Approach?
"Since the array is sorted and I need O(log n) time, binary search
is the perfect fit. I'll use the classic binary search template:
compare the target with the middle element and eliminate half the
search space based on the comparison. If I find the target, I return
its index immediately. If the loop ends without finding it, I return
-1. The key is using left + (right - left) / 2 for the mid calculation
to avoid integer overflow, and always updating pointers with ±1 to
ensure the search space shrinks."

Why O(log n)?
"Each comparison eliminates half of the remaining elements. So if
we have n elements, after k comparisons we have n/(2^k) elements.
When this becomes 1, we're done, which happens at k = log₂(n).
That's why it's O(log n)."

Edge Cases:
✓ Single element - handled by loop
✓ Target at boundaries - handled by comparisons
✓ Target not present - return -1
✓ Large arrays - no overflow with safe mid

📝 Quick Revision Notes

🎯 Core Concept:

Classic Binary Search: THE fundamental algorithm! Compare target with middle, eliminate half based on comparison. Loop: left <= right. Mid: left + (right - left) / 2. Return index if found, -1 if not.

⚡ Quick Implementation:

class Test {
  public int search(int[] a, int k) {
    int left = 0;
    int right = a.length - 1;

    while (left <= right) {
      int mid = left + (right - left) / 2;

      if(a[mid] == k) {
        return mid;
      } else if(a[mid] < k) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.search(new int[] {-1,0,3,5,9,12}, 9));
    System.out.println(t.search(new int[] {-1,0,3,5,9,12}, 2));
  }

}

🔑 Key Insights:

Pattern: Classic Binary Search (THE base template!)
Requirement: Array must be SORTED
Loop: left <= right (check single element)
Mid: left + (right - left) / 2 (safe from overflow)
Three Cases: =, <, > (standard comparisons)
Updates: Always mid ± 1 (avoid infinite loop)
Return: mid if found, -1 if not found
Eliminate: Half the search space each iteration
Time: O(log n), Space: O(1)

🎪 Memory Aid:

"Divide and Conquer! Check the MIDDLE, eliminate HALF!"
Think: "Left ≤ Right, Safe Mid, Compare, ±1!"

💡 The Key Insight:

Compare with middle:
  If equal: return mid (found!)
  If less: search left (right = mid - 1)
  If greater: search right (left = mid + 1)

Loop ends when left > right:
  Search space empty
  return -1 (not found)

⚠️ Critical Details:

1. Initialize: left = 0, right = n - 1
2. Loop: while (left <= right) ← Must be <=
3. Mid: left + (right - left) / 2 ← Safe!
4. Compare: if (nums[mid] == target)
5. Update: left = mid + 1 or right = mid - 1 ← Must be ±1
6. Return: mid or -1

🔥 Why Each Detail Matters:

left <= right (not <):
  Need to check when left == right
  Single element case: [5]

left + (right - left) / 2:
  Prevents integer overflow
  (left + right) / 2 can overflow!

mid ± 1:
  Ensures progress each iteration
  Without ±1: infinite loop risk

return -1:
  Standard way to indicate "not found"
  Loop ended, target doesn't exist

🎯 The Power of Binary Search:

Array size vs Comparisons:
  10 elements → 4 comparisons max
  100 elements → 7 comparisons max
  1,000 elements → 10 comparisons max
  1,000,000 elements → 20 comparisons max
  1,000,000,000 elements → 30 comparisons max

Compare with Linear Search:
  1,000,000 elements
  Linear: 1,000,000 comparisons
  Binary: 20 comparisons
  50,000x faster! 🚀

💡 The Invariant:

Loop Invariant:
  If target exists, it's in [left, right]

Each iteration:
  Check mid
  If not target, eliminate half
  Target still in remaining half

When left > right:
  Checked everything
  Target doesn't exist

🧪 Edge Cases

Case 1: Single element - found

Input: nums = [5], target = 5
Output: 0

Case 2: Single element - not found

Input: nums = [5], target = 3
Output: -1

Case 3: Target at beginning

Input: nums = [1, 2, 3, 4, 5], target = 1
Output: 0

Case 4: Target at end

Input: nums = [1, 2, 3, 4, 5], target = 5
Output: 4

Case 5: Target in middle

Input: nums = [1, 2, 3, 4, 5], target = 3
Output: 2

Case 6: Target not present

Input: nums = [1, 3, 5, 7, 9], target = 4
Output: -1

Case 7: Large array

Input: nums = [1..1000000], target = 999999
Output: 999998
Only ~20 comparisons! ✓

All handled correctly! ✓

🎓 Why This Problem Matters

This is THE foundation of binary search!

Learn this template:
  All other BS problems are variations

Common variations:
  - Find first/last occurrence
  - Find insert position  
  - Search in rotated array
  - Find peak element
  - Binary search on answer space

They all build on this base template!

Master this problem = Master binary search foundation!

Search Insert Position (LC 35) - Returns insert position instead of -1
First Bad Version (LC 278) - Find first occurrence pattern
Find First and Last Position (LC 34) - Extends to find range
Search in Rotated Sorted Array (LC 33) - Modified comparisons

Happy practicing! 🎯

Note: This is THE most important binary search problem! It's the foundation for all other BS problems. Master this template - you'll use it everywhere!

55. Binary Search

Problem Statement

🎨 Visual Understanding

The Problem Visualized

🚨 CRITICAL INSIGHT - Why Binary Search Works

Why O(log n)?

The Binary Search Invariant

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

Implementation

🔍 Dry Run

🎯 Why This Works - Deep Dive

The Classic Binary Search Template

⚠️ Common Mistakes to Avoid

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

🎓 Why This Problem Matters

Related Patterns