def bsearch(arr, low, high, x):
if (low <= high):
mid = (high + low)//2
if arr[mid] == x:
return arr[mid]
elif x > arr[mid]:
low = mid + 1
return (bsearch, low, high, x)
elif x < arr[mid]:
high = mid - 1
return (bsearch, low, high, x)
else:
return -1
def finitesearch(arr, x):
i = 1
listss = []
while i < len(arr):
listss.append(arr[i])
if (arr[i] == x):
return arr[i]
i = i * 2
return bsearch(arr, (len(listss) // 2)+1, len(listss) - 1, x)
def create_dynamic_array():
lst = []
## Works for 10, million records
for q in range(100000000):
lst.append(q)
return lst
lists = create_dynamic_array()
response = finitesearch(lists, 89898)
print(lists[: (list(response)[len(list(response))-1])])Imagine you have to return a target record among a total of millions of records and retrieve all the records before the target element.
Generally, having a million records means either your data set is high or you don’t know how many records are at the high end. In both cases, the below algorithm would work
The algorithm comprises three functions.
One is for creating a dynamic list where the high end is either unknown or high.
Second is where you iterate and go to the target element quickly using linear search
If the element is not present or the tracking variable is greater than the length of the list formed at that time (since this is a dynamic list), then go for a binary search to return the element to the main control.
The only trick here is to set the high and low end while calling the binary search.
I used an inner list to set the high and low, the moment when control comes out of the while loop, I take the position which is the last element of the list minus one as high end, and (len(list) // 2)+1 as lower end as we are multiplying by 2 in the stepper.
