Binary search: iterative and recursive

How it works (spec 10.3.2)

Compare the target with the middle item. If equal, stop. If the target is smaller, search the left half; if larger, the right half. Repeat until found or the section is empty (low > high). Each comparison halves the remaining items, so 1000 items need at most about 10 comparisons.

Iterative version

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        print("checking index", mid)
        if items[mid] == target:
            return mid
        elif target < items[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

data = [3, 8, 12, 15, 21, 30, 42]
print(binary_search(data, 30))

Output:

checking index 3
checking index 5
5

Recursive version

The recursive version passes low and high as parameters. The base cases are 'section empty' (return -1) and 'found' (return mid); otherwise it calls itself on one half.

def binary_search_rec(items, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if target < items[mid]:
        return binary_search_rec(items, target, low, mid - 1)
    return binary_search_rec(items, target, mid + 1, high)

data = [3, 8, 12, 15, 21, 30, 42]
print(binary_search_rec(data, 8, 0, len(data) - 1), binary_search_rec(data, 13, 0, len(data) - 1))

Output:

1 -1

Linear or binary?

Binary search is far faster on large lists but needs the list to be sorted first. Linear search works on any list and is fine for small ones.

Worked example

Trace a binary search for 21 in [3, 8, 12, 15, 21, 30, 42].

1. low 0, high 6, mid 3: 15 < 21, so low = 4
2. low 4, high 6, mid 5: 30 > 21, so high = 4
3. low 4, high 4, mid 4: 21 found

Answer: Found at index 4 after 3 comparisons

Check yourself

1. What is displayed when this code runs? ```python items = [2, 5, 7, 11, 13, 17, 19, 23, 29] target = 7 low = 0 high = len(items) - 1 while low <= high: mid = (low + high) // 2 print(mid, end=" ") if items[mid] == target: low = high + 1 elif target < items[mid]: high = mid - 1 else: low = mid + 1 ```
   Show answer

   4 1 2 . The midpoints checked are 4 1 2: 13 at index 4 is too big, 5 at index 1 too small, then 7 at index 2.

2. How many items are compared when searching for 29 in [2, 5, 7, 11, 13, 17, 19, 23, 29] with binary search?
   Show answer

   4. Indexes 4, 6, 7, 8 are checked: 4 comparisons.

3. What is the maximum number of comparisons a binary search needs for a sorted list of 100 items?
   Show answer

   7. Each comparison halves the list: 100, 50, 25, 12, 6, 3, 1 means at most 7 comparisons.

4. What is displayed when this code runs? ```python def binary_search(items, target): low = 0 high = len(items) - 1 while low <= high: mid = (low + high) // 2 if items[mid] == target: return mid elif target < items[mid]: high = mid - 1 else: low = mid + 1 return -1 print(binary_search([10, 20, 30, 40], 25)) ```
   Show answer

   -1. 25 is not in the list, so low passes high and -1 is returned.

5. Why can binary search not be used on the list [9, 2, 7, 4]?
   • It has an even number of items
   • It is not sorted, so discarding half the list could discard the target
   • It contains only integers
   • It is too short
   Show answer

   It is not sorted, so discarding half the list could discard the target. Discarding a half is only safe if everything in that half is known to be smaller or larger than the target.

6. This recursive binary search is missing its call for the right-hand half. Which line completes it? ```python def bsearch(items, target, low, high): if low > high: return -1 mid = (low + high) // 2 if items[mid] == target: return mid if target < items[mid]: return bsearch(items, target, low, mid - 1) __________ data = [1, 4, 6, 9, 12, 15] print(bsearch(data, 12, 0, 5), bsearch(data, 1, 0, 5), bsearch(data, 7, 0, 5)) ```
   • `bsearch(items, target, mid + 1, high)`
   • `return bsearch(items, target, mid, high)`
   • `return bsearch(items, target, low, mid + 1)`
   • `return bsearch(items, target, mid + 1, high)`
   Show answer

   `return bsearch(items, target, mid + 1, high)`. The right half starts just after mid, and the result of the recursive call must be returned.

7. In the recursive binary search, which condition is a base case that means the target is not present?
   • low == 0
   • low > high
   • mid == high
   • items[mid] > target
   Show answer

   low > high. When low passes high the section to search is empty.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (XCP01/YCP01), first teaching 2026
• Pearson IAL Computer Science Unit 2 Programming Language Subset (PLS), Python 3
• Pearson IAL Computer Science IAS sample assessment materials (Unit 2 paper and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.