Progressive Binary Search

Progressive Binary Search (also known as Exponential Search or Galloping Search) is an efficient algorithm for finding elements in sorted data streams where the size is unknown or very large. It combines exponential search with binary search to achieve optimal performance.

Core Concept

The algorithm works in two phases:

1. Exponential Search: Find the range containing the target by checking positions 1, 2, 4, 8, 16...
2. Binary Search: Perform standard binary search within the identified range\

Performance Characteristics

Comparison with Standard Binary Search

• Standard Binary Search: Requires knowing array size upfront
• Progressive Binary Search: Works with unknown or very large sizes
• Streaming Data: Ideal for data that arrives incrementally

Implementation Strategy

Key Design Decisions

1. Exponential Growth: Use powers of 2 for efficient range finding
2. Bounds Checking: Handle array boundaries carefully
3. Overflow Prevention: Use safe arithmetic to avoid integer overflow
4. Early Termination: Stop when target is found or range is determined

Implement a progressive binary search algorithm that efficiently finds elements in a large sorted stream. The algorithm should use exponential search (1, 2, 4, 8...) to find the upper bound, then perform binary search in the identified range. Optimize for streaming data where the size is unknown or very large.

#include <vector>
#include <algorithm>

/**
 * @brief Performs progressive binary search on a sorted array.
 * 
 * @param arr Sorted array to search in
 * @param target Value to find
 * @return Index of target if found, -1 otherwise
 */
int progressiveBinarySearch(const std::vector<int>& arr, int target) {
    // TODO: Handle edge cases (empty array, single element)
    // TODO: Implement exponential search to find range
    // TODO: Implement binary search within the range
    // TODO: Return index of target or -1 if not found

    return -1;
}