Base case
- Algorithms course
- Beginner
- Lesson 55/80
- 4 min
When low > high the element is not present.
Base case
Binary search's base case is left > right. This means the search range is empty and the target was not found.
In this case, -1 is returned. Since the while loop runs with left <= right, this condition naturally terminates.
Recursive binary search
Binary search can also be written recursively: search(arr, target, left, right). Base case: if left > right, return -1.
The recursive version may be more elegant but uses stack space. The iterative version is more efficient with O(1) memory.
Practice Recursive binary search
Write binary_rec(arr, target, left, right). Search recursively. Print 2 with print(binary_rec([2, 4, 6, 8], 6, 0, 3)).
Starter code
def binary_rec(arr, target, left, right):
# Search recursivelySample solution
def binary_rec(arr, target, left, right):
# Search recursively
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_rec(arr, target, mid + 1, right)
else:
return binary_rec(arr, target, left, mid - 1)
print(binary_rec([2, 4, 6, 8], 6, 0, 3))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Base case: match the terms
| Term | Meaning |
|---|---|
left > right |
Base |
return -1 |
Not found |
while |
Iterative |
Recursive |
Uses stack |
2 When does binary search return -1?
- When target is found
- When left > right Correct answer
- When array is empty
- When mid = 0
Explanation: It returns -1 when left > right.
3 Loop condition
while ____: loops.while left <= right: loops.Explanation: left <= right is right.