Binary Search

Not Started

Binary search is a divide-and-conquer algorithm that efficiently finds a target value in a sorted array. By eliminating half of the remaining elements with each comparison, it achieves logarithmic time complexity. This technique extends beyond simple searches to solving optimization problems.

Time Complexity: O(log n) - halves search space each iteration
Space Complexity: O(1) iterative, O(log n) recursive
Use Cases: Searching sorted arrays, finding boundaries, optimization problems
Requirement: Data must be sorted for binary search to work

Implementation Examples

# Python - Binary Search
def binary_search(arr, target):
    """Find target in sorted array"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Example: arr = [1,3,5,7,9], target = 5
# Output: 2
// C++ - Binary Search
int binarySearch(std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}
// C# - Binary Search
int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}
// Java - Binary Search
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

Common Patterns

Standard Search: Find exact target in sorted array
Left Boundary: Find first occurrence of target
Right Boundary: Find last occurrence of target
Optimization: Use binary search to find optimal value in monotonic functions