Binary Search Algorithm

Binary search is an efficient divide and conquer search algorithm that finds a target value in a sorted array by repeatedly dividing the search interval in half. It's much faster than linear search for large datasets, but requires the array to be sorted.

Interactive Visualization

Binary Search Visualization

Target:

Speed: 1000ms

Status: Click "Search" to start binary search visualization

Sorted Array Visualization

Not Searched

In Search Range

Low Pointer

High Pointer

Mid Pointer

Found Target

Discarded

How Binary Search Works:

• Divide: Calculate mid point of current search range

• Compare: Check if mid element equals, is less than, or greater than target

• Conquer: Discard half of the array based on comparison

• Repeat: Continue until target is found or range is empty

• Time Complexity: O(log n) - eliminates half each step

• Space Complexity: O(1) - only uses a few variables

• Prerequisite: Array must be sorted

• Efficiency: Much faster than linear search for large arrays

Divide and Conquer Strategy

Binary search exemplifies the divide and conquer paradigm by systematically eliminating half of the remaining search space in each iteration. This logarithmic reduction makes it incredibly efficient for large sorted datasets.

1. Divide

Find the middle element of the current search range

2. Compare

Compare the middle element with the target value

3. Conquer

Eliminate half the search space based on the comparison

🔑 Key Insight

By comparing with the middle element, we can determine which half of the array can contain our target (if it exists at all). This allows us to discard the other half entirely, reducing the problem size by 50% in each step.

⚠️ Critical Requirement: Sorted Array

Binary search only works on sorted arrays. This is not just a recommendation – it's a fundamental requirement for the algorithm's correctness.

Why Sorting is Essential

• Predictable Ordering: Comparison with middle element must indicate which half contains the target
• Elimination Logic: If middle > target, we know target can only be in the left half
• Search Space Reduction: Each comparison eliminates exactly half of the remaining elements
• Termination Guarantee: Algorithm will definitely terminate with correct result

Without Sorting

• Incorrect Results: May miss elements that are actually present
• False Positives: May incorrectly conclude element is absent
• No Performance Benefit: Cannot reliably eliminate half the search space
• Algorithm Breakdown: The fundamental assumption is violated

Example: Searching for 7

✅ Sorted Array: [1, 3, 5, 7, 9, 11, 13]

Step 1: mid = 7, target = 7 → Found!

Result: Found at index 3 ✓

❌ Unsorted Array: [13, 3, 9, 7, 1, 11, 5]

Step 1: mid = 7, target = 7 → Found!

Result: Lucky! But unreliable ⚠️

How Binary Search Works

Step-by-Step Process

Initialize: Set low = 0, high = array.length - 1

Calculate Mid: mid = low + (high - low) / 2

Compare: Check arr[mid] vs target

Eliminate: Adjust low or high to discard irrelevant half

Repeat: Continue until found or low > high

Case 1: Found

If arr[mid] == target:
Return mid (we found it!)

Case 2: Go Left

If arr[mid] > target:
Set high = mid - 1
(Target must be in left half)

Case 3: Go Right

If arr[mid] < target:
Set low = mid + 1
(Target must be in right half)

Pseudocode

ALGORITHM BinarySearch(arr[], n, target)
BEGIN
    // Initialize search bounds
    low = 0
    high = n - 1
    
    // Continue while search space is valid
    WHILE low <= high DO
        // Calculate middle index (avoid overflow)
        mid = low + (high - low) / 2
        
        // Check if middle element is the target
        IF arr[mid] == target THEN
            RETURN mid           // Found at index mid
        
        // Target is in the left half
        ELSE IF arr[mid] > target THEN
            high = mid - 1       // Eliminate right half
        
        // Target is in the right half
        ELSE
            low = mid + 1        // Eliminate left half
        END IF
    END WHILE
    
    // Target not found in array
    RETURN -1
END

// Recursive version
ALGORITHM BinarySearchRecursive(arr[], target, low, high)
BEGIN
    // Base case: invalid range
    IF low > high THEN
        RETURN -1
    END IF
    
    // Calculate middle index
    mid = low + (high - low) / 2
    
    // Found the target
    IF arr[mid] == target THEN
        RETURN mid
    
    // Search in left half
    ELSE IF arr[mid] > target THEN
        RETURN BinarySearchRecursive(arr, target, low, mid - 1)
    
    // Search in right half
    ELSE
        RETURN BinarySearchRecursive(arr, target, mid + 1, high)
    END IF
END

Complexity Analysis

Metric	Iterative	Recursive	Explanation
Time Complexity	O(log n)	O(log n)	Eliminates half the elements each step
Space Complexity	O(1)	O(log n)	Iterative uses constant space; recursive uses call stack
Max Comparisons	⌈log₂ n⌉	⌈log₂ n⌉	At most log base 2 of n comparisons needed

Why O(log n) Time?

• Half Elimination: Each comparison eliminates half the remaining elements
• Logarithmic Depth: Takes at most ⌈log₂ n⌉ steps to reduce n elements to 1
• Example: Array of 1000 elements needs at most 10 comparisons (2¹⁰ = 1024)
• Massive Efficiency: 1 million elements → only 20 comparisons!

Space Complexity Comparison

• Iterative O(1): Only uses a few variables (low, high, mid)
• Recursive O(log n): Each recursive call adds to the call stack
• Maximum Depth: Recursion depth equals number of iterations
• Preference: Iterative version is usually preferred for space efficiency

Binary Search vs Linear Search

Array Size: 1,000
Linear: 500 avg comparisons
Binary: 10 max comparisons
50x faster!

Array Size: 1,000,000
Linear: 500,000 avg comparisons
Binary: 20 max comparisons
25,000x faster!

Array Size: 1,000,000,000
Linear: 500,000,000 avg comparisons
Binary: 30 max comparisons
16,000,000x faster!

Code Examples

Here are implementations of binary search in different programming languages. Each version includes both iterative and recursive approaches, along with generic implementations and overflow-safe middle index calculation.

 def binary_search(arr, target):
    """
    Search for a target value in a sorted array using binary search.
    
    Args:
        arr: Sorted list of elements to search through
        target: The value to search for
    
    Returns:
        int: Index of target if found, -1 if not found
    
    Time Complexity: O(log n)
    Space Complexity: O(1)
    Prerequisite: Array must be sorted
    """
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        # Calculate middle index (avoid overflow in other languages)
        mid = left + (right - left) // 2
        
        # Found the target
        if arr[mid] == target:
            return mid
        # Target is in the left half
        elif arr[mid] > target:
            right = mid - 1
        # Target is in the right half
        else:
            left = mid + 1
    
    # Target not found
    return -1

def binary_search_recursive(arr, target, left=0, right=None):
    """
    Recursive implementation of binary search.
    Space Complexity: O(log n) due to recursion stack
    """
    if right is None:
        right = len(arr) - 1
    
    # Base case: invalid range
    if left > right:
        return -1
    
    # Calculate middle index
    mid = left + (right - left) // 2
    
    # Found the target
    if arr[mid] == target:
        return mid
    # Target is in the left half
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, left, mid - 1)
    # Target is in the right half
    else:
        return binary_search_recursive(arr, target, mid + 1, right)

# Example usage
if __name__ == "__main__":
    # Array must be sorted for binary search to work
    sorted_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    target = 7
    
    result = binary_search(sorted_numbers, target)
    
    if result != -1:
        print(f"Element {target} found at index {result}")
    else:
        print(f"Element {target} not found in the array")
    
    # Test with recursive version
    result_recursive = binary_search_recursive(sorted_numbers, 15)
    print(f"Recursive search result for 15: index {result_recursive}") 
 public class BinarySearch {
    
    /**
     * Search for a target value in a sorted array using binary search.
     * 
     * @param arr Sorted array to search through
     * @param target The value to search for
     * @return Index of target if found, -1 if not found
     * 
     * Time Complexity: O(log n)
     * Space Complexity: O(1)
     * Prerequisite: Array must be sorted
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // Calculate middle index (avoids integer overflow)
            int mid = left + (right - left) / 2;
            
            // Found the target
            if (arr[mid] == target) {
                return mid;
            }
            // Target is in the left half
            else if (arr[mid] > target) {
                right = mid - 1;
            }
            // Target is in the right half
            else {
                left = mid + 1;
            }
        }
        
        // Target not found
        return -1;
    }
    
    /**
     * Recursive implementation of binary search.
     * Space Complexity: O(log n) due to recursion stack
     */
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        // Base case: invalid range
        if (left > right) {
            return -1;
        }
        
        // Calculate middle index
        int mid = left + (right - left) / 2;
        
        // Found the target
        if (arr[mid] == target) {
            return mid;
        }
        // Target is in the left half
        else if (arr[mid] > target) {
            return binarySearchRecursive(arr, target, left, mid - 1);
        }
        // Target is in the right half
        else {
            return binarySearchRecursive(arr, target, mid + 1, right);
        }
    }
    
    /**
     * Convenience method for recursive binary search
     */
    public static int binarySearchRecursive(int[] arr, int target) {
        return binarySearchRecursive(arr, target, 0, arr.length - 1);
    }
    
    /**
     * Generic binary search that works with any Comparable type
     */
    public static <T extends Comparable<T>> int binarySearch(T[] arr, T target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int comparison = arr[mid].compareTo(target);
            
            if (comparison == 0) {
                return mid;
            } else if (comparison > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        // Array must be sorted for binary search to work
        int[] sortedNumbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;
        
        int result = binarySearch(sortedNumbers, target);
        
        if (result != -1) {
            System.out.println("Element " + target + " found at index " + result);
        } else {
            System.out.println("Element " + target + " not found in the array");
        }
        
        // Test with recursive version
        int resultRecursive = binarySearchRecursive(sortedNumbers, 15);
        System.out.println("Recursive search result for 15: index " + resultRecursive);
    }
} 
 #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * Search for a target value in a sorted vector using binary search.
 * 
 * @param arr Sorted vector to search through
 * @param target The value to search for
 * @return Index of target if found, -1 if not found
 * 
 * Time Complexity: O(log n)
 * Space Complexity: O(1)
 * Prerequisite: Vector must be sorted
 */
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left <= right) {
        // Calculate middle index (avoids integer overflow)
        int mid = left + (right - left) / 2;
        
        // Found the target
        if (arr[mid] == target) {
            return mid;
        }
        // Target is in the left half
        else if (arr[mid] > target) {
            right = mid - 1;
        }
        // Target is in the right half
        else {
            left = mid + 1;
        }
    }
    
    // Target not found
    return -1;
}

/**
 * Recursive implementation of binary search.
 * Space Complexity: O(log n) due to recursion stack
 */
int binarySearchRecursive(const vector<int>& arr, int target, int left, int right) {
    // Base case: invalid range
    if (left > right) {
        return -1;
    }
    
    // Calculate middle index
    int mid = left + (right - left) / 2;
    
    // Found the target
    if (arr[mid] == target) {
        return mid;
    }
    // Target is in the left half
    else if (arr[mid] > target) {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
    // Target is in the right half
    else {
        return binarySearchRecursive(arr, target, mid + 1, right);
    }
}

/**
 * Convenience function for recursive binary search
 */
int binarySearchRecursive(const vector<int>& arr, int target) {
    return binarySearchRecursive(arr, target, 0, arr.size() - 1);
}

/**
 * Template function for binary search that works with any type
 */
template<typename T>
int binarySearch(const vector<T>& arr, const T& target) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return -1;
}

/**
 * Using STL binary search functions
 */
void demonstrateSTLBinarySearch() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;
    
    // std::binary_search returns true/false
    bool found = binary_search(arr.begin(), arr.end(), target);
    cout << "STL binary_search: " << (found ? "Found" : "Not found") << endl;
    
    // std::lower_bound returns iterator to first element >= target
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() && *it == target) {
        cout << "STL lower_bound: Found at index " << (it - arr.begin()) << endl;
    }
}

int main() {
    // Vector must be sorted for binary search to work
    vector<int> sortedNumbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;
    
    int result = binarySearch(sortedNumbers, target);
    
    if (result != -1) {
        cout << "Element " << target << " found at index " << result << endl;
    } else {
        cout << "Element " << target << " not found in the array" << endl;
    }
    
    // Test with recursive version
    int resultRecursive = binarySearchRecursive(sortedNumbers, 15);
    cout << "Recursive search result for 15: index " << resultRecursive << endl;
    
    // Demonstrate STL functions
    demonstrateSTLBinarySearch();
    
    return 0;
} 

When to Use Binary Search

Perfect For

• Large Sorted Arrays: Massive performance advantage over linear search
• Frequent Searches: When you need to search the same dataset multiple times
• Database Indices: Foundation of many database indexing strategies
• Range Queries: Finding insertion points, lower/upper bounds
• Memory-Efficient Searches: O(1) space complexity with iterative version

Consider Alternatives When

• Unsorted Data: Sorting cost may outweigh search benefits
• Small Arrays: Linear search might be simpler and fast enough
• Frequent Insertions: Maintaining sorted order becomes expensive
• One-time Search: Sorting overhead not justified for single search

Real-World Applications

Common Uses: Database indexing, library catalogs, phone books, dictionary searches, git bisect, finding version in release history

Advanced Applications: Binary search on answer spaces, finding peak elements, searching in rotated arrays, interpolation search optimization