Overview

Binary Search is an efficient search algorithm that finds the position of a target value within a sorted array. The algorithm works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The key requirement for binary search is that the data structure must be sorted. This allows the algorithm to eliminate half of the remaining elements at each step, making it significantly faster than linear search for large datasets. Binary search can be implemented both iteratively and recursively, with the iterative approach generally being preferred for its better space efficiency.

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This logarithmic time complexity makes it extremely efficient for large datasets. The space complexity is O(1) for the iterative implementation and O(log n) for the recursive implementation due to the call stack.

How It Works

The algorithm works by:

1. Comparing the target with the middle element of the array
2. If they match, return the index
3. If the target is less than the middle element, search the left half
4. If the target is greater than the middle element, search the right half
5. Repeat until the element is found or the search space is exhausted

Algorithm Pseudocode

BinarySearch(arr, target):
    left = 0
    right = arr.length - 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  # Target not found
                

Implementation

Iterative Implementation

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
                

Recursive Implementation

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

Complexity Analysis

• Time Complexity: O(log n) - Each step eliminates half the search space
• Space Complexity: O(1) iterative, O(log n) recursive
• Best Case: O(1) - Target at the middle
• Worst Case: O(log n) - Target not found or at the edge

Common Trends in Problems where Binary Search is Applied

• Sorted Arrays: Binary search requires sorted data, making it perfect for problems involving sorted arrays or when you can sort the data first.
• Search Space Reduction: Problems where you need to eliminate half the search space at each step naturally fit binary search.
• Boundary Finding: Binary search excels at finding boundaries, such as the first or last occurrence of an element, or insertion points.
• Optimization Problems: When searching for a minimum or maximum value that satisfies certain conditions, binary search on the answer space is often the solution.
• Monotonic Functions: Problems involving monotonic functions (always increasing or decreasing) can often be solved using binary search.

Binary Search Framework

• Initialize left and right pointers to define the search space (typically 0 and n-1 for arrays).
• Use a while loop that continues while left <= right (or left < right depending on the problem).
• Calculate the middle index using left + (right - left) // 2 to avoid integer overflow.
• Compare the middle element with the target and adjust the search space accordingly.
• Handle edge cases carefully, especially when the target is not found or when dealing with duplicate values.

Search Variations

Finding First/Last Occurrence

When dealing with duplicate values, you might need to find the first or last occurrence of a target:

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
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result
                

Search in Rotated Array

Binary search can be adapted to work with rotated sorted arrays:

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
        
        # Left half is sorted
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1
                

Popular LeetCode Questions Using Binary Search

                    
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return -1
                    
                    

Related Algorithms

Explore other searching algorithms:

• Linear Search - Simple O(n) search for unsorted data
• Back to Searching Algorithms Overview