Binary search is a search method to improve efficiency by reducing the number of searches , It has an important premise is to ensure that the searched object is a sequential table , The steps and diagrams of binary search are as follows ：
First , Suppose the elements in the table are in ascending order , Compare the keywords recorded in the middle of the table with the search keywords , If the two are equal , Then the search is successful ;
Otherwise, use the middle position record to divide the table into front 、 Last two sub tables , If the key of the intermediate location record is greater than the search key , Then look up the previous sub table , Otherwise, look up the next sub table ;
Repeat the above process , Until you find the records that meet the conditions , Make the search successful , Or until the child table does not exist , The search is not successful at this time .
Non recursive implementation of binary search
# Non recursive implementation def binarySearch(alist, item): first = 0 last = len(alist) - 1 found = False while first <= last and not found: midpoint = (first + last) // 2 if alist[midpoint] == item: found = True else: if item < alist[midpoint]: last = midpoint - 1 else: first = midpoint + 1 return found binarySearch([2, 4, 5, 7, 8], 5)
Recursive implementation of binary search
# Recursive implementation def binarySearch(alist, item): if len(alist) == 0: return False else: midpoint = len(alist) // 2 if alist[midpoint] == item: return True else: if item < alist[midpoint]: return binarySearch(alist[:midpoint], item) else: return binarySearch(alist[midpoint + 1:], item) binarySearch([2, 4, 5, 7, 8], 5)