Algorithms in Python | Binary Search | Full Code | Telugu
#pythonintelugu #pythonalgorithms #naveenv
Algorithms in Python | Binary Search | Full Code with Time Complexity explanation| Telugu
Time Code:
00:00 Intro
04:16 Python Code
09:00 Integer Overflow
11:00 Document Strings
13:00 Time Complexity log n
Integer Overflow - https://en.wikipedia.org/wiki/Integer...
Binary Search
list_num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
item = 2
def bin_search(sequence, item):
"""
This function requires two position parameters
sequence-- list of sorted numbers &
item -- for the value to search
Then this function returns the index position if the item is found
else returns None
"""
begin = 0
end = len(sequence) - 1
while begin LT= end:
to avoid integer over flow
mid = begin + (end - begin) // 2
if sequence[mid] == item:
return mid
elif sequence[mid] GT item:
end = mid - 1
else:
begin = mid + 1
return None
TIME COMPLEXITY BINARY SEARCH
----------------------------------------------------------
= n x 1/2 x 1/2 x 1/2 x 1/2 x 1/2 x 1/2 x ½…..1/2k for k items
c= n/2k
If we solve for k =
• n = 2k Taking Log on both sides
• log n = log 2k
• k =log2n which is logarithmic time complexity
Time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm
Time Complexity is commonly expressed using big O notation, typically O(n), O (logn), O(n^2), O(2^n), O(n!) etc where n is the input size in units of bits needed to represent the input.
If you like this content, please like, share and subscribe. Motivates me to create more such content.