binary_search.py

#!/usr/bin/env python

importrandom
fromtypingimportList, Optional


defbinary_search(arr: List[int], lb: int, ub: int, target: int) ->Optional[int]:
"""
 A Binary Search Example which has O(log n) time complexity.
 """
whilelb<=ub:
mid=lb+ (ub-lb) //2
ifarr[mid] ==target:
returnmid
elifarr[mid] <target:
lb=mid+1
else:
ub=mid-1
return-1


defgenerate_random_list(size: int=10, lower: int=1, upper: int=50) ->List[int]:
returnsorted(random.randint(lower, upper) for_inrange(size))


deffind_target_in_list(target: int, lst: List[int]) ->int:
returnbinary_search(lst, 0, len(lst) -1, target)


defmain():
"""
 Executes the binary search algorithm with a randomly generated list.
 Time Complexity: O(log n)
 """
rand_num_li=generate_random_list()
target=random.randint(1, 50)
index=find_target_in_list(target, rand_num_li)
print(f"List: {rand_num_li}\nTarget: {target}\nIndex: {index}")


if__name__=='__main__':
main()