# Given list B = [2,5,7,8,9,11,14,16] find if 14 is present in this list or not.
def binarySearch(ls,data):
first = 0
last = len(ls)-1
while first<=last:
mid = (first+last)//2
if ls[mid] == data:
return True
else:
if ls[mid] > data:
last = mid-1
else:
first = mid+1
return False
print(binarySearch([2,5,7,8,9,11,14,16],4))
# Round First Last Mid ls[mid] Result
# 1 0 7 3 8 8<14
# 2 4 7 5 11 11<14
# 3 6 7 6 14 14=14
"""
NOTE: To find the mid element, “(first+last)//2” is used instead of “(first+last)/2”. This gives us whole
numbers especially when the length of the list is odd. Try 9/2 and 9//2 in your Python IDLE to get a
better understanding.
From the above explanation, it must be clear that Binary Search is consistently faster than Linear Search.
If you are familiar with o(n) notation, Linear Search is o(n) and Binary Search is log(n)
You can perform Linear Searches on a sorted list as well with a small optimization. You can stop the
search once the number to be found exceeds the element being compared to. For instance, you want to
search for 12 from the list [2,4,5,13,16,19], once you reach 13 you can stop because there is no way that
12 is going to come after 13 in a sorted list.
"""
