Saturday, September 11, 2021

Dynamic Programming - Binary Search - Index function to find 2*x+5 - O(Log n) - Better approach

Time Complexity is O(Log n) . Its better and faster without recursion.

from random import randint

import math

random_odd_numbers = list((val

for val in iter(lambda: randint(-64, 64), 0) if val % 2 != 0))

mylist = sorted(set(random_odd_numbers))

l = 0

h = len(mylist)

while ((h - l) > 1):

mid = math.ceil((l + h) / 2)

#print(mylist[mid], l, mid, h - 1)

if mylist[mid] == 2 * mid + 5 or(mylist[h - 1] == 2 * h + 5) or mylist[l] == 2 * l + 5:

print(2 * h + 5, "yes", mylist)

break

elif mylist[mid] < 2 * mid + 5:

l = mid

else :

h = mid