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.
اضغط تشغيل لرؤية المخرجات هنا.