Recursive binary search and random numbers
Esta página precisa de um navegador recente (com suporte a SharedArrayBuffer). Por favor, atualize Chrome, Edge, Firefox ou Safari para a versão mais recente.
English
Binary search, written recursively
- Lesson 07 searched a sorted list with a loop. Paper 4 also asks for the recursive version.
- Each call looks at the middle item. If it is not the target, the function calls itself on the half that could still hold it.
- Two base cases stop the calls: the item is found, or
Low > High, which means nothing is left to search.

English
def BinarySearch(Items, Target, Low, High):
if Low > High:
return -1
Mid = (Low + High) // 2
if Items[Mid] == Target:
return Mid
if Items[Mid] < Target:
return BinarySearch(Items, Target, Mid + 1, High)
return BinarySearch(Items, Target, Low, Mid - 1)
Numbers = [3, 8, 12, 19, 25, 31, 40]
print(BinarySearch(Numbers, 31, 0, len(Numbers) - 1))
print(BinarySearch(Numbers, 7, 0, len(Numbers) - 1))
- The output is
5, then-1(7 is not in the list). - Each recursive call is returned:
return BinarySearch(...). Without thereturn, the answer is lost and the function givesNone. - The first call passes the whole list:
Low = 0,High = len(Items) - 1.
English
Random numbers
import randomfirst.random.randint(1, 6)gives a whole number from 1 to 6, both included.random.random()gives a decimal from 0.0 up to, but not including, 1.0.random.seed(4)makes the same "random" numbers every run, which helps when you test.
import random
random.seed(4)
Dice = random.randint(1, 6)
print(1 <= Dice <= 6)
Fraction = random.random()
print(0 <= Fraction < 1)
Grid = [[random.randint(0, 9) for Col in range(3)] for Row in range(2)]
print(len(Grid), len(Grid[0]))
- Each line prints
Trueor a size: the values are random, but they are always in range. - Paper 4 uses random numbers to fill an array or a 2-D grid for testing, as in the last part of the example.
English
Common mistakes
| Wrong | Right | Why |
|---|---|---|
BinarySearch(Items, Target, Mid + 1, High) with no return |
return BinarySearch(...) |
the answer from the deeper call must be passed back |
BinarySearch(Items, Target, Mid, High) |
Mid + 1 |
the middle was already checked; using Mid can loop forever |
no Low > High test |
test it first | a missing item would recurse until Python stops it |
random.randint(0, 6) for a dice |
random.randint(1, 6) |
both ends are included |
random.random() * 6 for a dice |
random.randint(1, 6) |
random() gives a decimal, not a whole number |
English
Now you try
- Write the base cases first, then the two recursive calls.
- Press Check answer to test your code.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Write the recursive function BinarySearch(Items, Target, Low, High). It returns the index of Target in the sorted list Items, or -1 if it is not there.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Write MakeGrid(Rows, Cols), which returns a 2-D list with Rows rows and Cols columns, each cell a random whole number from 1 to 100.
Clique em Executar para ver a saída aqui.