You are given a sorted array of unique elements with an unknown size. You cannot directly access the array, but you can interact with it through an ArrayReader interface that provides a get(i) method. This method:

• Returns the value at index i (0-indexed) if i is within the array bounds
• Returns 2^31 - 1 if i is out of bounds

Given an integer target, your task is to find the index k where secret[k] == target. If the target doesn't exist in the array, return -1.

The challenge is to implement a search algorithm with O(log n) time complexity without knowing the array's size beforehand.

The solution uses a two-phase approach:

1. Finding the boundary: Start with r = 1 and keep doubling it (shifting left by 1 bit) while reader.get(r) < target. This exponential search helps locate an upper bound where the target must be before position r. Once reader.get(r) >= target, we know the target (if it exists) is between positions r/2 and r.

2. Binary search: With the range [l, r] established where l = r >> 1 (equivalent to r/2), perform a binary search for the first index whose value is greater than or equal to the target. Calculate mid = (l + r) // 2; when reader.get(mid) >= target, record mid as first_true_index and move r to mid - 1, otherwise move l to mid + 1. Finally, check if the element at first_true_index equals the target to determine the return value.

This approach efficiently handles the unknown array size by first establishing a search range in O(log n) time, then performing binary search within that range, maintaining the overall O(log n) complexity.

The key challenge here is that we don't know the array's size, so we can't apply binary search directly. In a typical binary search, we start with known boundaries [0, n-1]. But here, we need to first figure out where our search space ends.

Think of it like searching for a book in a library where you don't know how many shelves there are. You wouldn't check every single shelf linearly - that would be too slow. Instead, you'd make increasingly larger jumps to find roughly where the books end, then narrow down your search.

The insight is to use exponential growth to find an upper boundary. Why exponential? Because if we increment linearly (checking positions 1, 2, 3, 4...), we might need O(n) steps just to find the boundary. But if we double our position each time (checking positions 1, 2, 4, 8, 16...), we'll find a boundary in just O(log n) steps.

Once we overshoot the target (when reader.get(r) >= target), we know two crucial things:

1. The target, if it exists, must be before position r
2. The target must be after position r/2 (because if it were before r/2, we would have stopped earlier)

This gives us a bounded range [r/2, r] that contains at most r/2 elements. Now we can apply standard binary search within this range.

The beauty of this approach is that both phases - finding the boundary and searching within it - take O(log n) time. The exponential search grows as fast as possible to find the boundary, then binary search efficiently pinpoints the exact location. It's like zooming out quickly to get the big picture, then zooming in precisely to find what we need.

Pattern Learn more about Binary Search patterns.

The implementation follows a two-phase approach:

Phase 1: Finding the Search Boundary

We start by initializing r = 1 as our right boundary pointer. Then we enter a loop where we continuously double r by shifting it left (r <<= 1, equivalent to r * 2) as long as reader.get(r) < target. This exponential growth ensures we find a position where the value is greater than or equal to the target in O(log n) time.

Copy
r = 1
while reader.get(r) < target:
    r <<= 1

After this loop, we know:

• reader.get(r) >= target (or r is out of bounds, returning 2^31 - 1)
• reader.get(r/2) < target (from the previous iteration, when r > 1)

Phase 2: Binary Search in the Bounded Range

We set the left boundary l = r >> 1 (equivalent to r / 2). This gives us a search range [l, r] where the target must exist if it's in the array. In the code these pointers are named left and right.

Copy
left = right >> 1
first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if reader.get(mid) >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

The binary search looks for the first index whose value is greater than or equal to the target:

• Calculating the middle point: mid = (left + right) // 2
• If reader.get(mid) >= target, mid is a candidate, so we record it in first_true_index and continue searching the left half with right = mid - 1
• Otherwise, the answer is to the right of mid, so we set left = mid + 1

The loop ends when left > right. At that point first_true_index holds the smallest index in the range whose value is at least the target.

Final Check

After the binary search, first_true_index points to the position where the target should be if it exists. We verify by checking if reader.get(first_true_index) == target:

Copy
if first_true_index != -1 and reader.get(first_true_index) == target:
    return first_true_index
return -1

The use of bit shift operations (<< and >>) instead of multiplication and division is a common habit in competitive programming, though compilers usually optimize these operations automatically.