Binäärihaku (binary search) on algoritmi, joka etsii tehokkaasti alkiota järjestetystä listasta. Ideana on aloittaa haku listan keskeltä ja puolittaa hakualuetta sen perusteella, missä alkio voi sijaita.
Etsi tietoa binäärihausta netistä ja tutustu sen toimintaan.
Binäärihaku on yllättävän vaikea toteuttaa toimivasti. Esimerkiksi seuraava toteutus ei toimi oikein:
def binary_search(items, x):
left = 0
right = len(items) - 1
while left < right:
middle = (left + right) // 2
if items[middle] == x:
return True
if items[middle] > x:
right = middle - 1
else:
left = middle + 1
return False
numbers = [1, 3, 8]
print(binary_search(numbers, 2)) # False
print(binary_search(numbers, 3)) # True
print(binary_search(numbers, 4)) # False
Tutki yllä olevaa funktiota ja etsi kolme esimerkkiä syötteistä, joissa funktio ei toimi oikein.
Tässä tehtävässä saat pisteen automaattisesti, kun ilmoitat tulokset ja painat lähetysnappia.
Mitkä syötteet löysit ja miten löysit ne?
