Not the exercise. This adds up part of a list by passing positions down, rather than slicing off a new list at every step.
def total_between(items, start, end):
"""Sum items[start] through items[end], inclusive."""
if start > end: # an empty range
return 0
return items[start] + total_between(items, start + 1, end)
print(total_between([5, 1, 4, 2], 1, 2)) # -> 5 (1 + 4)
- The list never changes, the range does
Every call sees the same list and a smaller start..end. Nothing is copied, and a position means the same thing at every depth.
- An empty range is the base case
When start passes end there is nothing left, and the answer is known. start == end is not empty: it is one item, and it still counts.
- Slicing would change what an index means
items[1:] is a new list whose first item used to be at position 1. Any position found inside it is off by however much was sliced away.
Work out high when it is None, then look at the middle of low..high. It is either the target, too small or too big, and each of those tells you what to do next.
If low > high the range is empty: return -1. Otherwise mid = (low + high) // 2. Too small means the answer is right of mid, so search mid + 1..high; too big means low..mid - 1.
Pass items, target and the new low and high to binary_search, and return what it returns. Never slice the list: the positions must stay those of the original.
def binary_search(items, target, low=0, high=None): if high is None: high = len(items) - ____ if low > high: return ____ mid = (low + high) // 2 if items[mid] == target: return mid if items[mid] < target: return binary_search(items, target, ____, high) return binary_search(items, target, low, ____)
def binary_search(items, target, low=0, high=None):
if high is None:
high = len(items) - 1
if low > high:
return -1
mid = (low + high) // 2
if items[mid] == target:
return mid
if items[mid] < target:
return binary_search(items, target, mid + 1, high)
return binary_search(items, target, low, mid - 1)
mid has already been checked, so both halves leave it out. Passing mid itself can give a range that never shrinks: with low 3 and high 4, mid is 3 again, forever.
When low equals high there is still one item to look at. Stopping there is how a one-item list, or the last item of any list, goes unchecked.
items[mid + 1:] would be a copy whose index 0 is the original’s mid + 1, so the answer would have to be shifted back. Passing low and high keeps every index meaning the same thing, and copies nothing.
In real code use the bisect module: bisect_left finds the position in a sorted list and has been right for decades. Write it yourself to understand it, and because interviews still ask. And a Python loop is a better home for this than recursion, since the range halving makes the depth tiny but a loop has no depth at all.
- Return the position where target would be inserted when it is missing, like bisect_left does.
- Allow repeated values and return the first position of target.
- Write the loop version and check both agree on a thousand random lists.