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).

--

--

--

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Leaning pandas. Data manipulation and visualization. (COVID-19 in — Scotland statistics)

Raiden Pulse #13: News from July and August

Secure Database password using EC2 parameter store

Using Version Control With Unity

Using the Go execution tracer to speed up fractal rendering

An AI Web App Using Flask and Azure Cognitive Services

My First time using Rust, not so happy 🦀

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Annamariya Tharayil

Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

More from Medium

Longest Binary Subsequence Less Than or Equal to K

Twinkle Twinkle Little Star — a small project in Embedded Systems

Leetcode#1094. Car Pooling

Should I make class member variables const or constexpr?