Notes on Software Engineering Interviews
Some useful links:
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[0]
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