Cracking The Coding Interview Together – Problem 10.4: Sorted Search No Size

Imagine you are handed a sleek, highly optimized data stream wrapper by a legacy vendor. It stores sorted, positive integers, but there is a major catch: it does not expose a size() or length() method. The only interaction point is an elementAt(i) method that returns the element at index i in O(1) time—or -1 if you step outside the bounds. At first glance, you might think you are flying blind. How can you perform a binary search when you do not know where the array ends? This exact tension is the core conflict of Problem 10.4: Sorted Search, No Size. Together, we are going to explore how to combine exponential growth with targeted binary search to conquer this constraint efficiently.

Problem Statement

You are given an array-like data structure called Listy which lacks a size method. It features an elementAt(i) method that returns the element at index i in O(1) time. If i is beyond the bounds of the data structure, it returns -1. Given a Listy containing sorted, positive integers, our operational goal is to find the index at which a target element x occurs, returning -1 if the element is not present.

Analyze the Problem Together

Let us break down the constraints and hunt for the Aha! conflict. Standard binary search relies heavily on a known upper bound, typically arr.length - 1, to establish our initial search space. Without a size method, we do not know if our data structure has 10 elements or 10 billion elements.

If we try a naive linear scan from index 0 upwards, we invoke elementAt(i) one by one. While this works, our time performance degrades to O(N) where N is the index of the target. That completely defeats the purpose of leveraging the sorted nature of the data.

Instead, we need an approach that rapidly discovers an upper bound without overshooting catastrophically. This brings us to exponential search. We start with a small index boundary, say index = 1, and double it repeatedly (1, 2, 4, 8, 16...) until elementAt(index) either returns -1 or a value greater than or equal to our target x. Once we find this boundary, we have successfully bracketed our target inside a finite range, allowing us to execute a standard binary search.

Questions for the Interviewer

Before jumping to the IDE, a senior engineer always clarifies operational boundaries:

• Can the Listy contain duplicate elements? If so, do we need to return the first occurrence, or will any valid index suffice?
• Are we guaranteed that the integers inside Listy are strictly positive, meaning -1 is exclusively reserved for out-of-bounds indicators?
• What is the expected scale of the data structure? Will it fit in memory, or could it represent a massive, lazily-loaded stream?
• How is elementAt(i) implemented under the hood? Is there any network or disk I/O penalty we should minimize?

Think About the Solution

Our solution architecture splits cleanly into two distinct phases:

1. The Exponential Bound Discovery: We maintain an index variable starting at 1. While the element at our current index is not -1 and is less than our target x, we move our previous high bound to our current index and double our index. If elementAt(index) == -1, we know we have overshot the end of the structure, so our upper bound lies somewhere between our last valid index and the current index.
2. The Binary Search Phase: With our lower and upper bounds established, we perform a standard binary search. If we find the target, we return its index. If the search space collapses without a match, we return -1.

Let us watch out for edge cases: What if x is at index 0? What if Listy is empty (i.e., elementAt(0) == -1)? Our logic must handle these gracefully without throwing index out-of-bounds or null pointer exceptions.

Write Code and Explain

Here is our production-ready Java implementation. We have included comprehensive comments to guide you through each execution branch.

public class SortedSearchNoSize {

    // Mock interface for the Listy data structure
    public interface Listy {
        int elementAt(int i);
    }

    public static int search(Listy listy, int x) {
        // Handle edge case: if the very first element is out of bounds or invalid
        if (listy.elementAt(0) == -1 || listy.elementAt(0) > x) {
            return -1;
        }

        int index = 1;
        // Exponentially find the upper bound
        while (listy.elementAt(index) != -1 && listy.elementAt(index) < x) {
            index *= 2;
        }

        // Perform binary search within the discovered bounds
        int low = 0;
        int high = index;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int middleElement = listy.elementAt(mid);

            // If mid is out of bounds or greater than x, search left
            if (middleElement == -1 || middleElement > x) {
                high = mid - 1;
            } else if (middleElement < x) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }
}

Let us walk through this code step by step. First, we check index 0. If elementAt(0) is -1, the list is empty. If it exceeds x, because the array is sorted, x cannot possibly exist in the structure, so we exit early with -1.

Next, we enter our exponential search loop. We start at index = 1 and double it on each iteration as long as elementAt(index) is valid and smaller than x. Suppose our target is at index 9. Our index jumps 1 -> 2 -> 4 -> 8 -> 16. At 16, elementAt(16) is either -1 or greater than x. Our upper bound becomes 16, and our lower bound is safely set to 0 (or we can optimize low to the previous power of two, but 0 is safe and clean).

Finally, we run a classic binary search between low and high. Notice how we handle middleElement == -1: if our binary search midpoint lands past the end of the list, we treat it as too large and shrink our upper bound (high = mid - 1).

Time & Space Complexity

• Time Complexity: O(log P), where P is the index of the target element x. Finding the bounds takes O(log P) steps because we double the index each time. The subsequent binary search also takes O(log P) steps because the upper bound is at most twice the index of the target. Thus, the total time complexity remains logarithmic relative to the target's position.
• Space Complexity: O(1). We only allocate a few primitive integer variables (index, low, high, mid) for our pointers, making our auxiliary memory footprint constant.

Why This Problem Matters (The Senior Perspective)

Problems like Sorted Search, No Size teach us how to adapt classical algorithms to non-standard operational environments. In distributed systems and streaming architectures, we frequently encounter data streams or paginated APIs where total counts are expensive or impossible to compute upfront.

By mastering exponential search, you add a vital tool to your architectural belt for exploring unbounded or lazily-evaluated datasets. Whether you are querying database cursors, stream offsets, or memory-mapped files without metadata headers, the pattern of exponential probing followed by targeted binary search ensures optimal time complexity without risking resource exhaustion.

Final Thoughts

We successfully transformed an ambiguous data constraint into an efficient logarithmic search algorithm. Take some time to implement this in your preferred language, and try writing a custom mock Listy class to test various edge cases like missing elements and boundary overflows. Keep building, keep questioning your assumptions, and happy coding until next time!