Problem Description

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 standard binary search. Calculate mid = (l + r) >> 1, and adjust the boundaries based on whether reader.get(mid) is greater than or equal to the target. Finally, check if the element at position l 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.

Intuition

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.

Learn more about Binary Search patterns.

Solution Approach

The implementation follows the two-phase approach described in the reference solution:

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.

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)

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.

l = r >> 1
while l < r:
    mid = (l + r) >> 1
    if reader.get(mid) >= target:
        r = mid
    else:
        l = mid + 1

The binary search works by:

• Calculating the middle point: mid = (l + r) >> 1 (integer division)
• If reader.get(mid) >= target, the target is in the left half (including mid), so we set r = mid
• Otherwise, the target must be in the right half (excluding mid), so we set l = mid + 1

The loop continues until l == r, converging to a single position.

Final Check

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

return l if reader.get(l) == target else -1

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

Example Walkthrough

Let's walk through an example where we have a sorted array [1, 3, 5, 7, 9, 11, 13, 15] and we're searching for target = 9.

Phase 1: Finding the Search Boundary

Starting with r = 1:

• reader.get(1) = 3, and 3 < 9, so we double: r = 2
• reader.get(2) = 5, and 5 < 9, so we double: r = 4
• reader.get(4) = 9, and 9 >= 9, so we stop

Now we have r = 4 where reader.get(4) = 9 >= target.

Phase 2: Binary Search

Set l = r >> 1 = 4 >> 1 = 2. Our search range is [2, 4].

First iteration:

• l = 2, r = 4
• mid = (2 + 4) >> 1 = 3
• reader.get(3) = 7, and 7 < 9
• So we set l = mid + 1 = 4

Second iteration:

• l = 4, r = 4
• Loop terminates since l == r

Final Check

Check reader.get(4) = 9, which equals our target, so we return 4.

Let's trace another example where target = 10 (not in array):

Phase 1: Same as before, we end up with r = 4 (since reader.get(4) = 9 < 10 would cause another doubling to r = 8, and reader.get(8) returns 2^31 - 1 >= 10).

Phase 2: With l = 4, r = 8:

• First iteration: mid = 6, reader.get(6) = 13 > 10, set r = 6
• Second iteration: mid = 5, reader.get(5) = 11 > 10, set r = 5
• Third iteration: l = 4, r = 5, mid = 4, reader.get(4) = 9 < 10, set l = 5
• Loop terminates with l = r = 5

Final Check: reader.get(5) = 11 ≠ 10, so we return -1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log M), where M is the position of the target value in the array.

The algorithm consists of two phases:

1. Range Finding Phase: The first while loop doubles the index r (using r <<= 1) until we find a value greater than or equal to the target. Starting from index 1, this takes O(log M) iterations since we're exponentially increasing the search boundary. If the target is at position M, we need approximately log₂(M) doublings to reach an index beyond it.

2. Binary Search Phase: Once we've established the range [l, r] where l = r/2 and reader.get(r) >= target, we perform standard binary search. The size of this range is at most M, so binary search takes O(log M) time.

The total time complexity is O(log M) + O(log M) = O(log M).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables l, r, and mid, regardless of the input size. No additional data structures are created that scale with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Boundary Expansion

When doubling the right boundary (right <<= 1), the value can grow exponentially and potentially cause integer overflow in languages with fixed integer sizes. In Python, this isn't an issue due to arbitrary precision integers, but in languages like Java or C++, this could lead to unexpected behavior.

Solution: Add a check to ensure right doesn't exceed a reasonable maximum value (like 10^9 or the maximum array size constraint):

while reader.get(right) < target:
    if right > 10**9:  # Prevent excessive growth
        break
    right <<= 1

2. Incorrect Handling of Target at Index 0

The initial right = 1 means we start checking from index 1, potentially missing the target if it's at index 0. The algorithm assumes the exponential search will eventually include index 0 when left = right >> 1 is calculated, but this requires careful verification.

Solution: Add an explicit check for index 0 before starting the exponential search:

if reader.get(0) == target:
    return 0
right = 1

3. Misunderstanding the Binary Search Convergence

Developers might incorrectly assume left and right converge to different values or might use while left <= right instead of while left < right. This can lead to infinite loops or incorrect results.

Solution: Understand that the binary search invariant maintains that:

• When reader.get(mid) >= target, we set right = mid (not mid - 1)
• The loop terminates when left == right, pointing to the smallest index where value >= target
• This is crucial for finding the leftmost occurrence if duplicates existed

4. Not Handling Edge Case Where Target is Larger Than All Elements

If the target is larger than all elements in the array, the exponential search phase will eventually hit out-of-bounds indices, returning 2^31 - 1. The binary search will then search in a range that includes invalid indices.

Solution: The current implementation actually handles this correctly because:

• reader.get(right) will return 2^31 - 1 when out of bounds
• Since 2^31 - 1 > target, the binary search will proceed normally
• The final check reader.get(left) == target will correctly return -1

However, being explicit about this edge case in comments helps maintainability:

# Note: reader.get() returns 2^31 - 1 for out-of-bounds indices,
# which is larger than any valid target, ensuring correct behavior