Skip to main content
Talentd

Search in a Sorted Array of Unknown Size - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchInteractive8 min readAsked at: Google
Practice this problem

Problem Statement

This is an interactive problem.

You have a sorted array of unique elements and an unknown size. You do not have an access to the array but you can use the ArrayReader interface to access it. You can call ArrayReader.get(i) that:

  • returns the value at the ith index (0-indexed) of the secret array (i.e., secret[i]), or
  • returns 231 - 1 if the i is out of the boundary of the array.

You are also given an integer target.

Return the index k of the hidden array where secret[k] == target or return -1 otherwise.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: secret = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in secret and its index is 4.

Example 2:

Input: secret = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in secret so return -1.

 

Constraints:

  • 1 <= secret.length <= 104
  • -104 <= secret[i], target <= 104
  • secret is sorted in a strictly increasing order.

Approach Overview

Problem Overview: You need to search for a target value in a sorted array, but the array length is unknown. Instead of direct indexing, you access elements through an API like reader.get(i). If you read beyond the array boundary, the API returns a very large sentinel value. The challenge is locating the search boundaries before applying binary search.

Approach 1: Linear Scan (O(n) time, O(1) space)

The simplest approach is to start from index 0 and keep calling reader.get(i) while incrementing the index. Stop when the value equals the target or exceeds it. Because the array is sorted, once the returned value becomes larger than the target (or the sentinel value appears), the target cannot exist further. This approach works but is inefficient for large arrays because it may require scanning many elements sequentially.

Approach 2: Exponential Range Expansion + Binary Search (O(log n) time, O(1) space)

The efficient solution first discovers a valid search window using exponential expansion. Start with a small range such as [0, 1]. While reader.get(right) < target, double the right boundary (right *= 2). This quickly jumps across the array until the range contains the target or exceeds it. After identifying a range where the target could exist, run standard binary search between left and right.

Binary search repeatedly checks the middle index and narrows the search interval depending on whether the middle value is smaller or larger than the target. Because the array is sorted and the boundary was discovered through exponential growth, the search converges in logarithmic time.

This method combines two classic ideas: exponential search to determine bounds and binary search to locate the exact position. The algorithm only uses constant extra memory and interacts with the array through the provided interface, which makes it suitable for array-based search problems with hidden sizes.

Recommended for interviews: Exponential expansion followed by binary search is the expected approach. A quick mention of the linear scan demonstrates understanding of the problem constraints, but interviewers look for the logarithmic solution because it handles very large arrays efficiently and shows strong mastery of binary search patterns.

Solution

First, we define a pointer r = 1. Each time, we check if the value at position r is less than the target value. If it is, we multiply r by 2, i.e., shift it left by one bit, until the value at position r is greater than or equal to the target value. At this point, we can determine that the target value is within the interval [r / 2, r].

Next, we define a pointer l = r / 2, and then we can use the binary search method to find the position of the target value within the interval [l, r].

The time complexity is O(log M), where M is the position of the target value. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)Simple baseline when array size is small or when demonstrating brute force thinking
Exponential Range Expansion + Binary SearchO(log n)O(1)Optimal approach when array size is unknown and values are sorted

Video Solution

Search in Sorted Array of Unknown Size - Google Interview Question • Sandeep Kumar • 3,358 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Search in a Sorted Array of Unknown Size easy or hard?
The problem is generally rated Medium. The binary search itself is straightforward, but recognizing the need for exponential range expansion when the array size is unknown is the key insight that increases difficulty.
Search in a Sorted Array of Unknown Size Python/Java solution
The solution uses the same logic across languages: expand the search boundary exponentially and then perform binary search. Implementations are commonly written in Python, Java, C++, Go, and TypeScript using the provided ArrayReader interface.
How to solve Search in a Sorted Array of Unknown Size in O(log n)?
Start with a small window such as [0,1]. Keep doubling the right boundary while reader.get(right) is smaller than the target. Once the target lies within the discovered range, apply standard binary search between the left and right bounds to locate the exact index.
What is the best approach for Search in a Sorted Array of Unknown Size?
The optimal approach uses exponential range expansion followed by binary search. First double the search boundary until the value at that index is greater than or equal to the target. Then run binary search within that range. This method works in O(log n) time and O(1) space.
Is Search in a Sorted Array of Unknown Size asked at Google/Amazon/Meta?
Search problems involving unknown array sizes and binary search patterns frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of binary search variants and how to determine search boundaries efficiently.
What data structure is used in Search in a Sorted Array of Unknown Size?
The core structure is a sorted array accessed through an interface such as ArrayReader. The algorithm relies on binary search operations over the array indices while interacting with elements through API calls.
What is the time complexity of Search in a Sorted Array of Unknown Size?
The optimal solution runs in O(log n) time. Exponential expansion takes O(log n) steps to find a valid range, and binary search inside that range also takes O(log n). Space complexity remains O(1) since only a few pointers are used.

Ready to solve this problem?

Practice Search in a Sorted Array of Unknown Size with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Search

Next

Find the Index of the Large Integer