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.

Description Solution Video 13:21

702. Search in a Sorted Array of Unknown Size

Medium73.1% acceptance1 companyPremium elsewhere, free here

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 i^th index (0-indexed) of the secret array (i.e., secret[i]), or
returns 2³¹ - 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 <= 10⁴
-10⁴ <= secret[i], target <= 10⁴
secret is sorted in a strictly increasing order.

Asked at 1 company

Google

Topics

13:21

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

702. Search in a Sorted Array of Unknown Size

Asked at 1 company

Topics

Similar problems