jayk0001

Posted on Nov 6

DSA Fundamentals: Binary Search - From Theory to LeetCode Practice

#dsa #binarysearch #leetcode #algorithms

DSA Fundamentals: Binary Search - From Theory to LeetCode Practice

Binary Search is one of the most efficient searching algorithms, achieving O(log n) time complexity by repeatedly dividing the search space in half. Understanding binary search is essential for optimizing search operations and solving a wide variety of algorithmic problems beyond simple array searching.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core binary search patterns.

Understanding Binary Search

Binary Search Fundamentals

Binary Search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half, eliminating half of the remaining elements in each iteration.

Core Principle: Divide and Conquer

Instead of checking every element linearly (O(n)), binary search leverages the sorted property to make intelligent decisions:

Start with the entire array
Check the middle element
If target equals middle, found!
If target is less than middle, search left half
If target is greater than middle, search right half
Repeat until found or search space is empty

Why Binary Search is Fast

Comparison with Linear Search:

Array Size	Linear Search	Binary Search	Improvement
10	10 comparisons	4 comparisons	2.5× faster
100	100 comparisons	7 comparisons	14× faster
1,000	1,000 comparisons	10 comparisons	100× faster
1,000,000	1,000,000 comparisons	20 comparisons	50,000× faster

Mathematical Proof:

Each iteration cuts search space in half
After k iterations: n / 2^k elements remain
When 1 element left: n / 2^k = 1 → k = log₂(n)
Time Complexity: O(log n)

Prerequisites for Binary Search

Required:

Sorted data structure (or conceptually sorted search space)
Random access to elements (array, not linked list)
Clear comparison criteria (way to determine which half to search)

Binary Search Implementation Patterns

Pattern 1: Traditional Binary Search

Use case: Finding exact match in sorted array

Template:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        # Calculate middle (prevents integer overflow)
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid  # Found target
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half

    return -1  # Target not found

Key Points:

Middle calculation: left + (right - left) // 2 prevents integer overflow
- Alternative: (left + right) // 2 works in Python but can overflow in other languages
Loop condition: left <= right (inclusive)
Pointer update: mid + 1 or mid - 1 (exclude mid from next search)

Pattern 2: Conditional Binary Search

Use case: Finding minimum/maximum value satisfying a condition

Template:

def conditional_binary_search(arr):
    left = 0
    right = len(arr) - 1
    result = -1  # Track best answer found

    while left <= right:
        mid = left + (right - left) // 2

        if condition_satisfied(arr[mid]):
            result = arr[mid]  # Update result
            # Continue searching for better answer
            # (left or right depending on problem)
            right = mid - 1  # or left = mid + 1
        else:
            left = mid + 1  # or right = mid - 1

    return result

Key Points:

Track best answer found so far
Continue searching even after finding valid answer
Used for optimization problems (min/max)

Time and Space Complexity

Operation	Time Complexity	Space Complexity	Notes
Binary Search (iterative)	O(log n)	O(1)	Most common
Binary Search (recursive)	O(log n)	O(log n)	Recursion stack
Search in 2D matrix	O(log(m×n))	O(1)	Treat as 1D array
Rotated array search	O(log n)	O(1)	Modified binary search

Essential LeetCode Problems & Solutions

1. Binary Search (LeetCode 704)

Problem: Given a sorted array and target value, return the index of target if found, otherwise return -1.

Example:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4 (nums[4] = 9)

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1 (not found)

Approach: Classic binary search implementation. Compare middle element with target and eliminate half of search space each iteration.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            # Calculate middle index (prevents overflow)
            mid = left + (right - left) // 2

            # Found target
            if nums[mid] == target:
                return mid

            # Target in right half
            if nums[mid] < target:
                left = mid + 1
            # Target in left half
            else:
                right = mid - 1

        # Target not found
        return -1

Time Complexity: O(log n) - Halve search space each iteration

Space Complexity: O(1) - Only using pointers

Key Concepts:

Sorted array requirement: Essential for binary search
Middle calculation: left + (right - left) // 2 prevents overflow
Search space reduction: Eliminate half each iteration
Loop invariant: Target must be in [left, right] if it exists

Visualization:

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

Iteration 1: left=0, right=5, mid=2
  [-1, 0, 3, 5, 9, 12]
         ^
  nums[2]=3 < 9 → search right half

Iteration 2: left=3, right=5, mid=4
  [-1, 0, 3, 5, 9, 12]
               ^
  nums[4]=9 == 9 → Found! Return 4

2. Find Minimum in Rotated Sorted Array (LeetCode 153)

Problem: A sorted array has been rotated at an unknown pivot. Find the minimum element.

Example:

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

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0

Input: nums = [11, 13, 15, 17]
Output: 11 (no rotation)

Approach: Use binary search with custom logic. The minimum is where the rotation occurred. Compare middle with right to determine which half contains the minimum.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        min_val = float('inf')

        while left <= right:
            mid = left + (right - left) // 2

            # If mid > right, rotation point is in right half
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                # Mid could be minimum, update and search left
                min_val = min(min_val, nums[mid])
                right = mid - 1

        return min_val

Time Complexity: O(log n) - Binary search on rotated array

Space Complexity: O(1) - Only tracking minimum value

Key Concepts:

Rotation detection: Compare nums[mid] with nums[right]
Two sorted subarrays: Rotation creates two sorted segments
Minimum location: At the rotation point (smallest element)
Decision logic:
- If nums[mid] > nums[right]: minimum in right half (array rotated)
- Otherwise: minimum in left half or at mid

Visualization:

nums = [4, 5, 6, 7, 0, 1, 2]
        sorted →    ↑ rotation point (minimum)

Iteration 1: left=0, right=6, mid=3
  [4, 5, 6, 7, 0, 1, 2]
           ^        ^
  nums[3]=7 > nums[6]=2 → minimum in right half

Iteration 2: left=4, right=6, mid=5
  [4, 5, 6, 7, 0, 1, 2]
                 ^  ^
  nums[5]=1 < nums[6]=2 → update min=1, search left

Result: min_val = 0

Alternative Approach (Cleaner):

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2

            if nums[mid] > nums[right]:
                left = mid + 1  # Minimum in right half
            else:
                right = mid  # Mid could be minimum

        return nums[left]  # Left points to minimum

3. Search in Rotated Sorted Array (LeetCode 33)

Problem: Search for a target value in a rotated sorted array. Return its index or -1 if not found.

Example:

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

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

Approach: Modified binary search. Determine which half is sorted, then check if target is in that sorted half.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            # Found target
            if nums[mid] == target:
                return mid

            # Determine which half is sorted
            if nums[left] <= nums[mid]:
                # Left half is sorted
                if nums[left] <= target <= nums[mid]:
                    # Target in sorted left half
                    right = mid - 1
                else:
                    # Target in right half
                    left = mid + 1
            else:
                # Right half is sorted
                if nums[mid] <= target <= nums[right]:
                    # Target in sorted right half
                    left = mid + 1
                else:
                    # Target in left half
                    right = mid - 1

        return -1

Time Complexity: O(log n) - Modified binary search

Space Complexity: O(1) - Only using pointers

Key Concepts:

Identify sorted half: At least one half is always sorted
Range check: If target in sorted half's range, search it
Two cases: Left sorted vs right sorted
Decision tree:
1. Find which half is sorted (compare nums[left] with nums[mid])
2. Check if target is in sorted half's range
3. Search appropriate half

Visualization:

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

Iteration 1: left=0, right=6, mid=3
  [4, 5, 6, 7, 0, 1, 2]
   L        M        R
  nums[0]=4 <= nums[3]=7 → left half sorted
  4 <= 0 <= 7? NO → search right half

Iteration 2: left=4, right=6, mid=5
  [4, 5, 6, 7, 0, 1, 2]
               L  M  R
  nums[4]=0 <= nums[5]=1 → left half sorted? NO
  → right half sorted
  0 <= 0 <= 2? YES → search right half

Iteration 3: left=4, right=4, mid=4
  [4, 5, 6, 7, 0, 1, 2]
               ^
  nums[4]=0 == 0 → Found! Return 4

4. Search a 2D Matrix (LeetCode 74)

Problem: Search for a target value in an m×n matrix with properties:

Integers in each row are sorted left to right
First integer of each row is greater than last integer of previous row

Example:

Input: matrix = [[1, 3, 5, 7],
                 [10, 11, 16, 20],
                 [23, 30, 34, 60]], target = 3
Output: true

Input: matrix = [[1, 3, 5, 7],
                 [10, 11, 16, 20],
                 [23, 30, 34, 60]], target = 13
Output: false

Approach: Treat 2D matrix as flattened 1D sorted array. Convert 1D index to 2D coordinates using division and modulo.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])

        # Binary search on flattened array
        left = 0
        right = (rows * cols) - 1

        while left <= right:
            mid = left + (right - left) // 2

            # Convert 1D index to 2D coordinates
            row = mid // cols
            col = mid % cols
            mid_value = matrix[row][col]

            if mid_value == target:
                return True
            elif mid_value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

Time Complexity: O(log(m × n)) - Binary search on total elements

Space Complexity: O(1) - Only using pointers

Key Concepts:

1D to 2D conversion:
- row = index // cols (which row)
- col = index % cols (position in row)
Flattened view: Matrix is conceptually a sorted 1D array
Index mapping: Binary search on virtual 1D array

Visualization:

Matrix (2D):          Flattened (1D):
[ 1,  3,  5,  7]      [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
[10, 11, 16, 20]       0  1  2  3   4   5   6   7   8   9  10  11
[23, 30, 34, 60]

For index 5 (value 11):
  row = 5 // 4 = 1
  col = 5 % 4 = 1
  matrix[1][1] = 11 ✓

Binary search target=3:
  left=0, right=11, mid=5
  matrix[5//4][5%4] = matrix[1][1] = 11 > 3
  → search left half

  left=0, right=4, mid=2
  matrix[2//4][2%4] = matrix[0][2] = 5 > 3
  → search left half

  left=0, right=1, mid=0
  matrix[0//4][0%4] = matrix[0][0] = 1 < 3
  → search right half

  left=1, right=1, mid=1
  matrix[1//4][1%4] = matrix[0][1] = 3 == 3
  → Found!

5. Koko Eating Bananas (LeetCode 875)

Problem: Koko loves bananas. There are n piles with different amounts. She can eat at most k bananas per hour. Find the minimum k such that she can eat all bananas within h hours.

Example:

Input: piles = [3, 6, 7, 11], h = 8
Output: 4

Explanation:
- k=4: 1 + 2 + 2 + 3 = 8 hours ✓
- k=3: 1 + 2 + 3 + 4 = 10 hours ✗ (too slow)

Approach: Binary search on eating speed. Search space is [1, max(piles)]. For each speed, calculate if Koko can finish in h hours.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Search space: minimum speed 1, maximum speed max(piles)
        left = 1
        right = max(piles)
        result = right

        while left <= right:
            k = (left + right) // 2

            # Calculate total hours needed at speed k
            total_hours = sum(math.ceil(pile / k) for pile in piles)

            # Can finish in time?
            if total_hours <= h:
                # This speed works, try slower (minimize k)
                result = min(k, result)
                right = k - 1
            else:
                # Too slow, need faster speed
                left = k + 1

        return result

Time Complexity: O(n × log m) where n = number of piles, m = max(piles)

Space Complexity: O(1) - Only tracking result and pointers

Key Concepts:

Non-traditional search space: Searching for speed, not array index
Condition check: Can Koko finish with speed k?
Minimization: Find minimum k that satisfies condition
Ceiling division: math.ceil(pile / k) for partial hours
Binary search on answer: Search the solution space directly

Why Binary Search Works:

Monotonic property: If speed k works, all speeds > k also work
Search space: [1, max(piles)] - clear boundaries
Condition: Can finish in h hours (yes/no)

Detailed Example:

piles = [3, 6, 7, 11], h = 8

Search space: [1, 11]

Iteration 1: k=6
  Hours: ceil(3/6) + ceil(6/6) + ceil(7/6) + ceil(11/6)
       = 1 + 1 + 2 + 2 = 6 ≤ 8 ✓
  Update result=6, try slower: right=5

Iteration 2: k=3
  Hours: ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3)
       = 1 + 2 + 3 + 4 = 10 > 8 ✗
  Too slow, need faster: left=4

Iteration 3: k=4
  Hours: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4)
       = 1 + 2 + 2 + 3 = 8 ≤ 8 ✓
  Update result=4, try slower: right=3

Iteration 4: left=4, right=3 → left > right, stop
Result: 4

6. Time Based Key-Value Store (LeetCode 981)

Problem: Design a time-based key-value store that:

Stores multiple values for same key at different timestamps
Retrieves value at given timestamp (or closest previous timestamp)

Operations:

set(key, value, timestamp): Store value at timestamp
get(key, timestamp): Get value at or before timestamp

Example:

["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation:
- set("foo", "bar", 1)
- get("foo", 1) → "bar" (exact match)
- get("foo", 3) → "bar" (timestamp 1 is closest ≤ 3)
- set("foo", "bar2", 4)
- get("foo", 4) → "bar2" (exact match)
- get("foo", 5) → "bar2" (timestamp 4 is closest ≤ 5)

Approach: Use hash map where each key stores list of [value, timestamp] pairs. Timestamps are strictly increasing (per problem), so use binary search to find value at or before given timestamp.

class TimeMap:
    def __init__(self):
        # key -> list of [value, timestamp] pairs
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # Initialize list if key doesn't exist
        if key not in self.store:
            self.store[key] = []

        # Append [value, timestamp] pair
        self.store[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        result = ""

        # Get all values for this key
        values = self.store.get(key, [])

        # Key doesn't exist
        if not values:
            return result

        # Binary search for largest timestamp <= given timestamp
        left = 0
        right = len(values) - 1

        while left <= right:
            mid = left + (right - left) // 2

            # values[mid] = [value, timestamp]
            if values[mid][1] <= timestamp:
                # This timestamp works, save it and search for later one
                result = values[mid][0]
                left = mid + 1
            else:
                # Timestamp too large, search left
                right = mid - 1

        return result

Time Complexity:

set: O(1) - Append to list
get: O(log n) - Binary search on timestamps list

Space Complexity: O(n) - Store all key-value-timestamp entries

Key Concepts:

Hash map + sorted lists: Each key has chronologically sorted values
Binary search on timestamps: Find largest timestamp ≤ query
Closest previous value: Not exact match required
Monotonic timestamps: Guarantees sorted order in each list

Visualization:

After: set("foo", "bar", 1), set("foo", "bar2", 4), set("foo", "bar3", 7)

store = {
  "foo": [
    ["bar", 1],
    ["bar2", 4],
    ["bar3", 7]
  ]
}

get("foo", 5):
  Binary search for timestamp ≤ 5

  left=0, right=2, mid=1
  values[1][1] = 4 ≤ 5 ✓
  result = "bar2", search right for potentially larger
  left = 2

  left=2, right=2, mid=2
  values[2][1] = 7 > 5 ✗
  Search left
  right = 1

  left=2, right=1 → stop
  result = "bar2"

Core Binary Search Patterns

Pattern 1: Traditional Binary Search (Exact Match)

When to use:

Searching for exact value in sorted array
Need index of target element
Clear match condition

Template:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Examples: Binary Search (704), Search Insert Position

Pattern 2: Finding Boundary (First/Last Occurrence)

When to use:

Finding first or last occurrence
Finding insertion point
Range queries

Template:

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left for first
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

Pattern 3: Binary Search on Answer Space

When to use:

Minimizing/maximizing a value
Search space is not an array but a range
Monotonic condition (if x works, x+1 also works or vice versa)

Template:

def binary_search_on_answer(min_val, max_val):
    left, right = min_val, max_val
    result = max_val

    while left <= right:
        mid = left + (right - left) // 2
        if condition_satisfied(mid):
            result = mid
            right = mid - 1  # Try to minimize
        else:
            left = mid + 1
    return result

Examples: Koko Eating Bananas, Capacity To Ship Packages, Split Array Largest Sum

Pattern 4: Rotated/Modified Sorted Array

When to use:

Array is sorted but rotated
Modified sorted properties
Need to identify which part is sorted

Template:

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid

        # Identify which half is sorted
        if arr[left] <= arr[mid]:  # Left half sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Examples: Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array

Pattern 5: 2D Binary Search

When to use:

2D matrix with sorted properties
Can treat as flattened 1D array
Row-wise or column-wise sorting

Template:

def search_2d_matrix(matrix, target):
    if not matrix:
        return False

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2
        row, col = mid // cols, mid % cols

        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

Examples: Search a 2D Matrix, Search a 2D Matrix II

Performance Optimization Tips

1. Prevent Integer Overflow

# Potentially unsafe in languages with fixed integer size
mid = (left + right) // 2  # Could overflow if left + right > MAX_INT

# Safe: prevents overflow
mid = left + (right - left) // 2  # Always safe

# Alternative in Python (no overflow issues)
mid = (left + right) // 2  # Fine in Python (arbitrary precision)

Key insight: Python has arbitrary precision integers, but use safe version for language portability.

2. Choose Correct Loop Condition

# Use <= when you need to check left == right case
while left <= right:
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

# Use < when mid could be answer (find minimum/boundary)
while left < right:
    mid = left + (right - left) // 2
    if condition(arr[mid]):
        right = mid  # Mid could be answer
    else:
        left = mid + 1

return left  # or right (they're equal)

3. Early Termination for Edge Cases

# Check impossible cases first
def binary_search(arr, target):
    if not arr:
        return -1
    if target < arr[0] or target > arr[-1]:
        return -1  # Target outside array range

    # ... regular binary search

4. Use Built-in Functions When Appropriate

import bisect

# bisect_left: leftmost insertion point
index = bisect.bisect_left(arr, target)

# bisect_right: rightmost insertion point
index = bisect.bisect_right(arr, target)

# But implement manually for interviews!

Common Pitfalls and Solutions

1. Infinite Loop with Wrong Pointer Updates

# Wrong: May cause infinite loop
while left < right:
    mid = (left + right) // 2
    if condition(arr[mid]):
        right = mid  # OK
    else:
        left = mid  # ❌ When left = mid, infinite loop!

# Correct: Always make progress
while left < right:
    mid = (left + right) // 2
    if condition(arr[mid]):
        right = mid
    else:
        left = mid + 1  # ✓ Always moves forward

2. Off-by-One Errors in Boundary Conditions

# Common mistake: wrong initial right boundary
right = len(arr)  # ❌ Out of bounds!
right = len(arr) - 1  # ✓ Correct

# In 2D matrix
right = rows * cols  # ❌ Should be cols - 1
right = (rows * cols) - 1  # ✓ Correct

3. Forgetting to Update Result in Conditional Search

# Wrong: Not saving best answer found
while left <= right:
    mid = left + (right - left) // 2
    if condition(mid):
        right = mid - 1  # ❌ Lost this valid answer!
    else:
        left = mid + 1

# Correct: Save result before continuing
result = -1
while left <= right:
    mid = left + (right - left) // 2
    if condition(mid):
        result = mid  # ✓ Save this answer
        right = mid - 1
    else:
        left = mid + 1
return result

4. Wrong Comparison in Rotated Array

# Wrong: Comparing with wrong boundary
if nums[mid] > nums[left]:  # ❌ Doesn't always identify sorted half

# Correct: Use <= for left comparison
if nums[left] <= nums[mid]:  # ✓ Handles duplicates correctly

5. Incorrect Ceiling Division

# Wrong: Integer division truncates
hours = sum(pile / k for pile in piles)  # Float result

# Correct: Use ceiling division
import math
hours = sum(math.ceil(pile / k) for pile in piles)

# Alternative: Integer arithmetic
hours = sum((pile + k - 1) // k for pile in piles)

Binary Search Time Complexity Analysis

Comparison with Other Search Algorithms

Algorithm	Worst Case	Average Case	Best Case	Space	Prerequisite
Linear Search	O(n)	O(n)	O(1)	O(1)	None
Binary Search	O(log n)	O(log n)	O(1)	O(1)	Sorted array
Jump Search	O(√n)	O(√n)	O(1)	O(1)	Sorted array
Interpolation	O(n)	O(log log n)	O(1)	O(1)	Uniformly distributed

Binary search is optimal for sorted arrays: Can't do better than O(log n) for comparison-based search.

When NOT to Use Binary Search

Unsorted data: Sorting costs O(n log n), not worth it for single search
Linked lists: No O(1) random access (need O(n) to reach middle)
Small arrays: Linear search might be faster due to simplicity
Frequent insertions/deletions: Maintaining sorted order is expensive

Problem Complexity Summary

Problem	Type	Time Complexity	Space Complexity	Key Pattern
Binary Search (704)	Traditional	O(log n)	O(1)	Exact match
Find Min Rotated (153)	Rotated Array	O(log n)	O(1)	Conditional search
Search Rotated (33)	Rotated Array	O(log n)	O(1)	Identify sorted half
Search 2D Matrix (74)	2D Search	O(log(m×n))	O(1)	Flatten to 1D
Koko Bananas (875)	Answer Space	O(n × log m)	O(1)	Binary search on k
TimeMap (981)	Data Structure	O(log n) get	O(n)	Binary search on time

Conclusion

Binary Search is one of the most elegant and efficient algorithms in computer science, achieving O(log n) performance through divide-and-conquer strategy. Key takeaways:

Core Concepts Mastered:

Binary Search Fundamentals:

O(log n) time complexity: Fastest search algorithm for sorted data
Divide and conquer: Eliminate half of search space each iteration
Requirements: Sorted array, random access, clear comparison criteria
Loop invariants: Maintain left <= right and target in search space

Essential Patterns Mastered:

Pattern 1: Traditional binary search (exact match finding)

Pattern 2: Conditional binary search (optimization problems)

Pattern 3: Rotated array search (identify sorted portions)

Pattern 4: 2D binary search (flatten and search)

Pattern 5: Binary search on answer space (non-traditional search spaces)

Problem-Solving Strategies:

Identify sorted property: Essential for binary search
Choose loop condition: <= for exact match, < for boundary finding
Save best answer: In optimization problems, track result before continuing
Calculate middle safely: Use left + (right - left) // 2
Update pointers correctly: mid + 1 or mid - 1 to avoid infinite loops

Key Optimization Principles:

Prevent overflow in middle calculation (though not issue in Python)
Early termination for edge cases (empty array, out of range)
Choose right pattern based on problem type
Store indices when you need to calculate distances
Verify loop termination to avoid infinite loops

When to Use Binary Search:

Searching in sorted array
Finding boundaries (first/last occurrence)
Optimization problems with monotonic property
Search space has ordered property
Need O(log n) performance

Advanced Applications:

Finding peak element in mountain array
Allocating minimum pages/packages
Finding k-th smallest element
Median of two sorted arrays
Square root calculation

Next Steps:

Building on binary search foundations, future topics will cover:

Binary Search Trees (BST operations and traversals)
Advanced Binary Search (finding k-th element, median)
Trie and Prefix Trees (efficient string search)
Graph Search Algorithms (DFS, BFS with optimization)

The problems covered here represent fundamental binary search patterns that appear across technical interviews and competitive programming. Master these patterns, and you'll recognize binary search opportunities in optimization and search problems.

Practice Problems for Mastery:

Basic Binary Search:

704. Binary Search
35. Search Insert Position
374. Guess Number Higher or Lower
278. First Bad Version
69. Sqrt(x)

Finding Boundaries:

34. Find First and Last Position of Element in Sorted Array
744. Find Smallest Letter Greater Than Target
162. Find Peak Element

Rotated Arrays:

33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II (with duplicates)
153. Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II

2D Search:

74. Search a 2D Matrix
240. Search a 2D Matrix II
378. Kth Smallest Element in a Sorted Matrix

Binary Search on Answer:

875. Koko Eating Bananas
1011. Capacity To Ship Packages Within D Days
410. Split Array Largest Sum
1482. Minimum Number of Days to Make m Bouquets
1283. Find the Smallest Divisor Given a Threshold

Advanced:

4. Median of Two Sorted Arrays
981. Time Based Key-Value Store
1201. Ugly Number III
1268. Search Suggestions System

References:

NeetCode - Algorithms
Binary Search Tutorial - TopCoder
LeetCode Patterns
Introduction to Algorithms by Cormen et al.
Algorithm Design Manual by Steven Skiena

This comprehensive guide provides a solid foundation for mastering binary search algorithm and recognizing binary search patterns in algorithmic problem-solving.