Search in a Sorted Array of Unknown Size — Day 105(Python)

Photo by Markus Winkler on Unsplash

Today’s question is a medium-tagged question. Let’s go!

702. Search in a Sorted Array of Unknown Size

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 2^31 - 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^4
• -104 <= secret[i], target <= 10^4
• secret is sorted in a strictly increasing order.

We know that we need to search for an element in a sorted array. This means that we will be using binary search. (Hint: Searching in sorted array = Binary Search).

One additional condition is, we do not know the length of the array that needs to be searched. But we do know the max length of the array possible. Hence we will assume the length of the array is max length.

If you have doubts or need a refresher regarding Binary Search, please follow this link.

Alright, let’s look into the code.

# """
# 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:
        low = 0
        high = pow(10,4)
        while(low <= high):
            mid = (low + high) //2
            out = reader.get(mid)
            if(out == target):
                return mid
            elif(target < out):
                high = mid - 1
            else:
                low = mid + 1
        return -1

Complexity Analysis

Time Complexity

Every time we look for the target on our list, we are dividing our list by half. Hence time complexity is O(logN), where N is the max length.

Space Complexity

We are making use of constant space while we perform binary search and hence space complexity is O(1).

We can solve binary search through recursion too. When we are planning to use recursion, we need to identify the base condition. In this case, our base conditions are when low is greater than high then we would return -1 i.e. we did not find the required number, or we found the target.

Until we reach the Base condition, we keep dividing our array in half. Let us look into the code.

# """
# 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:
        def binarysearch(low, high, reader, target):
            if(low > high):
                return -1
            mid = (low + high) //2
            out = reader.get(mid)
            if(out == target):
                return mid
            elif(target < out):
                high = mid - 1
                return binarysearch(low, high, reader, target)
            else:
                low = mid + 1
                return binarysearch(low, high, reader, target)
        low = 0
        high = pow(10,4)
        output = binarysearch(low, high, reader, target)
        return output

Complexity Analysis

Time Complexity

Every time we look for the target on our list, we are dividing our list by half. Hence time complexity is O(logN), where N is the max length.

Space Complexity

Since recursion internally uses stack, space complexity is O(logN).