LeetCode 702: Search in a Sorted Array of Unknown Size Solution

Master LeetCode problem 702 (Search in a Sorted Array of Unknown Size), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

702. Search in a Sorted Array of Unknown Size

Medium

Array Binary Search Interactive

Problem Explanation

Explanation:

Given a sorted array of unknown size and a target value, we need to find if the target exists in the array and return its index. We are not provided with the size of the array. We can approach this problem by using a binary search algorithm with an optimized search space.

Start with an index low = 0 and high = 1.
Check if the target value lies between the low and high indices by comparing the target value with the element at index high.
If the target value is greater than the element at index high, update low = high and high = 2 * high to expand the search space.
Perform binary search within the range [low, high] to find the target value.

This approach helps in dynamically expanding the search space based on the target value and ensuring that the binary search is performed within a valid range.

Time Complexity: O(log n) - where n is the index of the target element within the array. Space Complexity: O(1)

Solution Code

class Solution {
    public int search(ArrayReader reader, int target) {
        int low = 0, high = 1;
        while (reader.get(high) < target) {
            low = high;
            high *= 2;
        }
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (reader.get(mid) == target)
                return mid;
            else if (reader.get(mid) < target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 702 (Search in a Sorted Array of Unknown Size)?

This page provides optimized solutions for LeetCode problem 702 (Search in a Sorted Array of Unknown Size) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

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

The time complexity for LeetCode 702 (Search in a Sorted Array of Unknown Size) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 702 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 702 in Java, C++, or Python.

Back to LeetCode Solutions