How hard is LeetCode 702. Search in a Sorted Array of Unknown Size?

LeetCode 702. Search in a Sorted Array of Unknown Size is rated Medium on LeetCode.

What is the time complexity of LeetCode 702. Search in a Sorted Array of Unknown Size?

The Python solution on this page runs in O(\log M), where M is the position of the target value.

What is the space complexity of LeetCode 702. Search in a Sorted Array of Unknown Size?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 702. Search in a Sorted Array of Unknown Size cover?

LeetCode 702. Search in a Sorted Array of Unknown Size is tagged Array, Binary Search and Interactive on LeetCode.

Is LeetCode 702. Search in a Sorted Array of Unknown Size a premium problem?

Yes. LeetCode 702. Search in a Sorted Array of Unknown Size is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Search in a Sorted Array of Unknown Size — LeetCode 702 Python Solution

MediumLeetCode PremiumArrayBinary SearchInteractive

Problem: #702
Pattern: Monotonic Stack
Reading time: 4 min
Source: leetcode.com

The problem

This is an interactive problem. You have a sorted array of unique elements and an unknown size.

Example

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

Python solution

Python

# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# class ArrayReader:
#    def get(self, index: int) -> int:


class Solution:
    def search(self, reader: "ArrayReader", target: int) -> int:
        r = 1
        while reader.get(r) < target:
            r <<= 1
        l = r >> 1
        while l < r:
            mid = (l + r) >> 1
            if reader.get(mid) >= target:
                r = mid
            else:
                l = mid + 1
        return l if reader.get(l) == target else -1

Complexity

Measure	Complexity
Time	O(\log M), where M is the position of the target value
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 702. Search in a Sorted Array of Unknown Size is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 702. Search in a Sorted Array of Unknown Size?: LeetCode 702. Search in a Sorted Array of Unknown Size is rated Medium on LeetCode.
What is the time complexity of LeetCode 702. Search in a Sorted Array of Unknown Size?: The Python solution on this page runs in O(\log M), where M is the position of the target value.
What is the space complexity of LeetCode 702. Search in a Sorted Array of Unknown Size?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 702. Search in a Sorted Array of Unknown Size cover?: LeetCode 702. Search in a Sorted Array of Unknown Size is tagged Array, Binary Search and Interactive on LeetCode.
Is LeetCode 702. Search in a Sorted Array of Unknown Size a premium problem?: Yes. LeetCode 702. Search in a Sorted Array of Unknown Size is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.