Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Search in a Sorted Infinite Array (medium)

Problem Statement

Given an infinite sorted array (or an array with unknown size), find if a given number ‘key’ is present in the array. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

Since it is not possible to define an array with infinite (unknown) size, you will be provided with an interface ArrayReader to read elements of the array. ArrayReader.get(index) will return the number at index; if the array’s size is smaller than the index, it will return Integer.MAX_VALUE.

Example 1:

.....

.....

.....

Like the course? Get enrolled and start learning!
O

origamimathematician

· 4 months ago

One of the constraints is: reader is sorted in a strictly increasing order.

But one of your test cases is: [1, 1, 1, 1, 1, 1, 1, 2] 1

[1, 1, 1, 1, 1, 1, 1, 2] is not strictly increasing if we are using the standard mathematical definition of strictly increasing. You should rephrase this constraint, its a bit confusing as is.

S

Shubham Das

· 4 years ago

Can anyone tell this is which leetcode problem?

Show 1 reply
P

PKK

· 3 years ago

Hi,

I get "Unable to execute code." message when running any solution. Please fix it.

Thanks

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

import math
import sys 

class Solution:
  def searchInfiniteSortedArray(self, reader, key):
    
    # figure out the reader size by doing binary search between 0 and the 
    # largest integer possible = sys.maxsize
    def find_array_last_index():
      b, e = 0, sys.maxsize
      index = 0
      while b <= e:
        m = (b + e) // 2
        if reader.get(m) == math.inf:
          e = m - 1
        else:
          b = m + 1
          index = m 
      return index
    
    # do a binary search to find the first occurrence of the key 
    def search(length):
      b, e = 0, length
      index = -1
      while b <= e:
        m = (b + e) // 2
        if reader.get(m) >= key:
          index = m
          e = m - 1
        else:
          b = m + 1
      return index if reade