Python Tricks #14 - Binary search is faster than linear

# 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.
"""