40 Algorithms Every Programmer Should Know

Binary Search

The pre-requisite of the binary search algorithm is sorted data. The algorithm iteratively divides a list into two parts and keeps a track of the lowest and highest indices until it finds the value it is looking for:

def BinarySearch(list, item):    first = 0    last = len(list)-1    found = False while first<=last and not found:             midpoint = (first + last)//2             if list[midpoint] == item:                     found = True             else:                     if item < list[midpoint]:                             last = midpoint-1                     else:                             first = midpoint+1     return found

The output is as follows:

Note that calling the BinarySearch function will return True if the value is found in the input list.