Implementera binärsökning

I den här videon lärde du dig hur man implementerar linjärsökning och binärsökning och såg skillnaderna mellan dem.

I den här övningen ska du implementera funktionen binary_search(). Klarar du det?

Den här övningen är en del av kursen

Datastrukturer och algoritmer i Python

Visa kurs

Övningsinstruktioner

Kontrollera om sökvärdet är lika med värdet i mitten.
Kontrollera om sökvärdet är mindre än värdet i mitten.
Sätt last till värdet av middle minus ett.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1
  
  while first <= last:
    middle = (first + last)//2
    # Check whether the search value equals the value in the middle
    if ____ == ____:
      return True
    # Check whether the search value is smaller than the value in the middle
    elif ____ < ____:
      # Set last to the value of middle minus one
      ____
    else:
      first = middle + 1
  return False
  
print(binary_search([1,5,8,9,15,20,70,72], 5))

Redigera och kör kod