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