Home/

...

/

Search in a Sorted Infinite Array (medium)

Search in a Sorted Infinite Array (medium)

Dry-run tables

The following is the implementation of the solution provided for the Search in a Sorted Infinite Array (medium) problem:

Press + to interact
Python 3.5
import math
class ArrayReader:
  def __init__(self, arr):
    self.arr = arr
  def get(self, index):
    if index >= len(self.arr):
      return math.inf
    return self.arr[index]
def search_in_infinite_array(reader, key):
  # find the proper bounds first
  start, end = 0, 1
  while reader.get(end) < key:
    newStart = end + 1
    end += (end - start + 1) * 2
    # increase to double the bounds size
    start = newStart
  return binary_search(reader, key, start, end)
def binary_search(reader, key, start, end):
  while start <= end:
    mid = start + (end - start) // 2
    if key < reader.get(mid):
      end = mid - 1
    elif key > reader.get(mid):
      start = mid + 1
    else:  # found the key
      return mid
  return -1
def main():
  reader = ArrayReader([4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30])
  print(search_in_infinite_array(reader, 16))
  print(search_in_infinite_array(reader, 11))
  reader = ArrayReader([1, 3, 8, 10, 15])
  print(search_in_infinite_array(reader, 15))
  print(search_in_infinite_array(reader, 200))
main()

Sample input #1

Input: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], key = 16

Line number

Function

Loop iteration

mid

start

end

reader.get(end)

17

search_in_infinite_array

-

-

0

1

6

18-22

search_in_infinite_array

-

-

2

5

14

18-22

search_in_infinite_array

-

-

6

13

30

33

binary_search

-

-

6

13

-

28-35

binary_search

1

9

6

8

-

28-35

binary_search

2

7

6

6

-

28-35

binary_search

3

6

-

-

-

Sample input #2

Students may be encouraged to fill the dry-run table with the following input:

Input: [1, 3, 8, 10, 15], key = 15

Line number

Function

Loop iteration

mid

start

end

reader.get(end)

17

search_in_infinite_array

-

-

0

1

3

18-22

search_in_infinite_array

-

-

2

5

inf

...

...

...

...

...

...

...

Step-by-step solution construction

The first step in the algorithm is finding proper bounds of the array to perform binary search. We’ll start with bound size =1= 1 and then exponentially increase it (double it), until we find the bounds that can have the key.

This is done in the search_in_infinite_array() function below:

Press + to interact
Python 3.8
from cmath import inf
import math
class ArrayReader:
  def __init__(self, arr):
    self.arr = arr
  def get(self, index):
    if index >= len(self.arr):
      return math.inf
    return self.arr[index]
def printReader(reader):
  output = ""
  i = 0
  while reader.get(i) != inf:
      output += str(reader.get(i)) + ", "
      i+=1
  output = "[" + output[:-2] + "]"
  print("Given array: ", output, sep = "")
def search_in_infinite_array(reader, key):
  # find the proper bounds first
  printReader(reader)
  print("key:", key, "\n")
  start, end = 0, 1
  print("Start index: ", start)
  print("End index: ", end)
  j = 1
  while reader.get(end) < key:
    print("\tLoop iteration: ", j, sep = "")
    j+=1
    print("\t\treader.get(end): ", reader.get(end), sep = "")
    newStart = end + 1
    print("\t\tstart: ", start, ", end: ", end, sep = "")
    print("\t\tUpdated start: end + 1 --> ",end, " + 1 = ", newStart, sep = "")
    end += (end - start + 1) * 2
    # increase to double the bounds size
    start = newStart
    print("\t\tUpdated end: end + ((end - start + 1) * 2) = ",end, sep = "" )
    print("")
  print("\tSince now, reader.get(end) > key: ", reader.get(end), " > ", key, " --> we stop here.")
  print("")
  print("Bounds: ", start, " <-->  ", end,", size: ", end - start + 1, sep = "")
  print("")
def main():
  reader = ArrayReader([4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30])
  reader2 = ArrayReader([1, 3, 8, 10, 15])
  inputarrays = [(reader, 16), (reader, 11), (reader2, 15), (reader2, 200)]
  for i in inputarrays:
    index = search_in_infinite_array(i[0], i[1])
    if index:
      print("The key is present at index ", index, " in the array.", sep = "")
    else:
      print("The key is not present in the array.")
    print("-"*100+"\n")
main()

Next, we’ll use the above bounds to perform binary search. This is done in the binary_search() function.

  • start is updated when key is greater than reader.get(end).
  • end is updated when key is less than reader.get(end).
Press + to interact
Python 3.8
from cmath import inf
import math
class ArrayReader:
  def __init__(self, arr):
    self.arr = arr
  def get(self, index):
    if index >= len(self.arr):
      return math.inf
    return self.arr[index]
def printReader(reader):
  output = ""
  i = 0
  while reader.get(i) != inf:
      output += str(reader.get(i)) + ", "
      i+=1
  output = "[" + output[:-2] + "]"
  print("Given array: ", output, sep = "")
def search_in_infinite_array(reader, key):
  # find the proper bounds first
  printReader(reader)
  print("key:", key, "\n")
  start, end = 0, 1
  print("Start index: ", start)
  print("End index: ", end)
  j = 1
  while reader.get(end) < key:
    print("\tLoop iteration: ", j, sep = "")
    j+=1
    print("\t\treader.get(end): ", reader.get(end), sep = "")
    newStart = end + 1
    print("\t\tstart: ", start, ", end: ", end, sep = "")
    print("\t\tUpdated start: end + 1 --> ",end, " + 1 = ", newStart, sep = "")
    end += (end - start + 1) * 2
    # increase to double the bounds size
    start = newStart
    print("\t\tUpdated end: end + ((end - start + 1) * 2) = ",end, sep = "" )
    print("")
  print("\tSince now, reader.get(end) > key: ", reader.get(end), " > ", key, " --> we stop here.")
  print("")
  print("Bounds: ", start, " <-->  ", end,", size: ", end - start + 1, sep = "")
  print("")
  return binary_search(reader, key, start, end)
def binary_search(reader, key, start, end):
  j = 1
  while start <= end:
    print("\tLoop iteration: ", j, sep = "")
    j+=1
    print("\t\tstart: ", start, ", end: ", end, sep = "")
    mid = start + (end - start) // 2
    print("\t\tmid: (start + end)/2 = ", mid, sep = "")
    if key < reader.get(mid):
      print("\t\tkey < reader.get(mid): ", key, " < ", reader.get(mid), " --> update end to search in first half of range", sep = "")
      end = mid - 1
      print("\t\tUpdated end: mid - 1 --> ",mid, " - 1 = ",  end, sep = "")
    elif key > reader.get(mid):
      print("\t\tkey > reader.get(mid): ", key, " > ", reader.get(mid), " --> update start to search in second half of range", sep = "")
      start = mid + 1
      print("\t\tUpdated start: mid + 1 --> ",mid, " + 1 = ",  start, sep = "")
    else:  # found the key
      print("\t\tkey found --> returning mid: ", mid, sep = "")
      return mid
    print("")
  return -1
def main():
  reader = ArrayReader([4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30])
  reader2 = ArrayReader([1, 3, 8, 10, 15])
  inputarrays = [(reader, 16), (reader, 11), (reader2, 15), (reader2, 200)]
  for i in inputarrays:
    index = search_in_infinite_array(i[0], i[1])
    print("")
    if index == -1:
      print("The key is not present in the array.")
    else:
      print("The key (", i[1], ") is present at index ", index, " in the array.", sep = "")
    print("-"*100+"\n")
main()