Recursive binary search and random numbers
이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
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.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
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.
출력을 보려면 '실행'을 클릭하세요.
난이도 3/5 · 200코인 + 오늘 첫 완료 시 작은 보너스 추가
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.
출력을 보려면 '실행'을 클릭하세요.