Recursive binary search and random numbers
Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
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.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Nhấn Chạy để xem kết quả ở đây.