 Brian T. Liao
Jun 20, 2019 • 1 min read

# Notes on Software Engineering Interviews

### Search an Infinitely Sized List

The idea is we double our lower and upper bounds until the element is in the bounds. The element is not in the array of infinite numbers only if the number is less than the smallest number. If the element is larger, then we will keep doubling.

The complexity will be O(log(p)) where p is the last high number greater than the element. Doubling takes O(log(p)) and binary search takes O(log(p)).

``````def find_elm(arr, elm):
low, high, cur = 0, 1, arr
while cur < elm:
low = high
high = 2 * high
cur = arr[high]
#
return binary_search(arr, low, high, elm)

def binary_search(arr, low, high, elm):
if low < high:
mid = low + (high - low) // 2
if arr[mid] == elm:
return mid
if arr[mid] < elm:
return binary_search(arr, low, mid - 1, elm)
else: # arr[mid] >= elm
return binary_search(arr, mid + 1, high, elm)
return -1
``````

I’ll see if I can write some stuff and have it help me practice!

Post by: Brian T. Liao