Binary Search

Binary search is a divide-and-conquer algorithm that finds an element in a sorted array by repeatedly halving the search space.

How It Works

1. Compare target with middle element
2. If target equals middle → found
3. If target < middle → search left half
4. If target > middle → search right half
5. Repeat until found or search space is empty

Visual Example

Sorted Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23

Step 1: low=0, high=9, mid=4 → arr[4]=16 < 23 → search right
Step 2: low=5, high=9, mid=7 → arr[7]=56 > 23 → search left
Step 3: low=5, high=6, mid=5 → arr[5]=23 = 23 → FOUND!

Iterative Implementation (Preferred)

public int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;  // Prevents overflow
        
        if (arr[mid] == target) {
            return mid;  // Found
        } else if (arr[mid] < target) {
            low = mid + 1;  // Search right half
        } else {
            high = mid - 1;  // Search left half
        }
    }
    
    return -1;  // Not found
}

Recursive Implementation

public int binarySearchRecursive(int[] arr, int target, int low, int high) {
    if (low > high) {
        return -1;  // Base case: not found
    }
    
    int mid = low + (high - low) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, high);
    } else {
        return binarySearchRecursive(arr, target, low, mid - 1);
    }
}

Why low + (high - low) / 2?

// WRONG: Can cause integer overflow
int mid = (low + high) / 2;
// If low = 1,000,000,000 and high = 2,000,000,000
// low + high = 3,000,000,000 > Integer.MAX_VALUE

// CORRECT: Prevents overflow
int mid = low + (high - low) / 2;
// Equivalent to low + (high - low) / 2
// Both expressions give same result, but second is safe

Complexity Analysis

Variation 1: Finding First Occurrence

Useful when array has duplicates.

public int findFirst(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int result = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            result = mid;      // Record position
            high = mid - 1;    // Continue searching left
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return result;
}

Variation 2: Finding Last Occurrence

public int findLast(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int result = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            result = mid;      // Record position
            low = mid + 1;     // Continue searching right
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return result;
}

Variation 3: Finding Floor and Ceil

Floor: Largest element ≤ target
Ceil: Smallest element ≥ target

// Floor - largest element <= target
public int findFloor(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int result = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] <= target) {
            result = arr[mid];
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return result;
}

// Ceil - smallest element >= target
public int findCeil(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int result = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] >= target) {
            result = arr[mid];
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    
    return result;
}

When to Use Binary Search

1. Sorted array - classic binary search
2. Monotonic function - function that only increases or decreases
3. Search space is ordered - can eliminate half each step
4. Finding minimum/maximum with constraint - binary search on answer

Common Mistakes

1. Off-by-one errors - low <= high vs low < high
2. Integer overflow - use low + (high - low) / 2
3. Infinite loops - ensure low and high always change
4. Wrong midpoint calculation - always use safe formula