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 .

 Insert picture description here

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)
Please bring the original link to reprint ,thank
Similar articles