# Interview essential algorithm ｜ the idea and implementation of binary search (Python)

#### Two points search

​ 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
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)
``````