Binärsökning
def br_search(v, target):
"""Returns True if the sorted list v contains target and False
otherwise.
Undefined behaviour if v is not sorted"""
return helper(v, 0, len(v), target)
def helper(v, start, end, target):
if start > end or start >= len(v):
return False
mid = (start+end) // 2
if v[mid] == target:
return True
if v[mid] < target:
return helper(v, mid+1, end, target)
else:return helper(v, start, mid-1, target)
def test_br_search():
TEST_SIZE = 10
for length in range(TEST_SIZE):
v = []
for i in range(length):
v.append(i)
for current in v:
assert br_search(v, current)
assert not br_search(v, TEST_SIZE)
Kopieras listan som pekas ut av v vid ett anrop till br_search? Hur är det med anrop till helper? Vilka basfall och rekursiva anrop förekommer i koden kan någon vara snäll och peka ut dessa?
Tack på förhand
När du gör ett anrop till br_search så skapas det en referens v till listan som du anger som parameter i anropet. Så efter anropet har du två referenser (en i funktionen och en utanför) till samma objekt (lista i det här fallet). Exempelvis:
v = [1, 2, 3] //Här skapar jag en referens v till listan [1, 2, 3].
br_search(v, target). // När jag gör detta anrop skapas en till referens v till samma lista [1, 2, 3], som finns innanför funktionen. Du skapar alltså inte en kopia av listan, du har fortfarande samma lista men du har skapat en annan variabel som refererar till den. Detta gäller inte nödvändigtvis i andra språk.
Helper är din rekursiva funktion i det här fallet. Innan jag försöker hjälpa mer, förstår du hur en rekursiv funktion fungerar? Ser du varför helper är en rekursiv funktion? Basfall i en rekursiv funktion används för att avsluta själva rekursionen, kan du se vilka de är?
