Binary Search Using Recursion: flowchart, algorithm and program
This program reads n sorted numbers and a key, then finds the key with a recursive binarySearch function. Each call looks at the middle element and throws away half of the remaining range, so the search is very fast.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read n.
- Step 3: Set i = 0.
- Step 4: If i < n, go to step 5; otherwise go to step 7.
- Step 5: Read arr[i].
- Step 6: Set i = i + 1. Go to step 4.
- Step 7: Read key.
- Step 8: Set result = binarySearch(arr, 0, n-1, key).
- Step 9: If low > high, go to step 10; otherwise go to step 11.
- Step 10: Return -1. Go to step 17.
- Step 11: Set mid = (low + high) / 2.
- Step 12: If arr[mid] == key, go to step 13; otherwise go to step 14.
- Step 13: Return mid. Go to step 17.
- Step 14: If key < arr[mid], go to step 15; otherwise go to step 16.
- Step 15: Search left: binarySearch(low, mid-1). Go to step 9.
- Step 16: Search right: binarySearch(mid+1, high). Go to step 9.
- Step 17: If result == -1, go to step 18; otherwise go to step 19.
- Step 18: Print Key not found. Go to step 20.
- Step 19: Print Key found at result + 1.
- Step 20: Stop.
Program in C, Python and Java
Binary Search Using Recursion program in C
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (key < arr[mid])
return binarySearch(arr, low, mid - 1, key);
else
return binarySearch(arr, mid + 1, high, key);
}
int main() {
int n, i, key, result;
int arr[100];
printf("Enter n: ");
scanf("%d", &n);
printf("Enter %d sorted numbers: ", n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Enter key: ");
scanf("%d", &key);
result = binarySearch(arr, 0, n - 1, key);
if (result == -1)
printf("Key not found\n");
else
printf("Key found at position %d\n", result + 1);
return 0;
}Binary Search Using Recursion program in Python
def binary_search(arr, low, high, key):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif key < arr[mid]:
return binary_search(arr, low, mid - 1, key)
else:
return binary_search(arr, mid + 1, high, key)
n = int(input("Enter n: "))
arr = list(map(int, input("Enter " + str(n) + " sorted numbers: ").split()))
key = int(input("Enter key: "))
result = binary_search(arr, 0, n - 1, key)
if result == -1:
print("Key not found")
else:
print("Key found at position", result + 1)Binary Search Using Recursion program in Java
import java.util.Scanner;
public class Main {
static int binarySearch(int[] arr, int low, int high, int key) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (key < arr[mid])
return binarySearch(arr, low, mid - 1, key);
else
return binarySearch(arr, mid + 1, high, key);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
int[] arr = new int[n];
System.out.print("Enter " + n + " sorted numbers: ");
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
System.out.print("Enter key: ");
int key = sc.nextInt();
int result = binarySearch(arr, 0, n - 1, key);
if (result == -1)
System.out.println("Key not found");
else
System.out.println("Key found at position " + (result + 1));
}
}
Sample input: n = 6, numbers = 5 12 18 23 40 56, key = 23
Output: Enter n: Enter 6 sorted numbers: Enter key: Key found at position 4
How it works
- main() reads n, fills arr[0..n-1] with the sorted numbers, reads key, and calls binarySearch(arr, 0, n - 1, key) over the whole array.
- Base case 1: if low > high, the range is empty, so the key is not present and the function returns -1.
- Otherwise mid = (low + high) / 2. If arr[mid] == key, the function returns mid, which is the index of the key.
- If key < arr[mid], the key can only be on the left, so it recurses on (low, mid - 1). Otherwise it recurses on (mid + 1, high).
- For the sample 5 12 18 23 40 56 with key 23: low=0, high=5 gives mid=2 (18), and 23 > 18 so low becomes 3. Then mid=4 (40), and 23 < 40 so high becomes 3. Then mid=3 (23), which is a match, so index 3 is returned and main() prints position 3 + 1 = 4.
Dry run (trace table)
| Step | Line | Box | n | i | arr[0] | arr[1] | arr[2] | arr[3] | arr[4] | arr[5] | key | low | high | mid | result | Output |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 15 | Start | ||||||||||||||
| 2 | 19 | Read n | 6 | |||||||||||||
| 3 | 21 | i = 0 | 6 | 0 | ||||||||||||
| 4 | 21 | i < n? | 6 | 0 | ||||||||||||
| 5 | 22 | Read arr[i] | 6 | 0 | 5 | |||||||||||
| 6 | 21 | i = i + 1 | 6 | 1 | ||||||||||||
| 7 | 21 | i < n? | 6 | 1 | ||||||||||||
| 8 | 22 | Read arr[i] | 6 | 1 | 12 | |||||||||||
| 9 | 21 | i = i + 1 | 6 | 2 | ||||||||||||
| 10 | 21 | i < n? | 6 | 2 | ||||||||||||
| 11 | 22 | Read arr[i] | 6 | 2 | 18 | |||||||||||
| 12 | 21 | i = i + 1 | 6 | 3 | ||||||||||||
| 13 | 21 | i < n? | 6 | 3 | ||||||||||||
| 14 | 22 | Read arr[i] | 6 | 3 | 23 | |||||||||||
| 15 | 21 | i = i + 1 | 6 | 4 | ||||||||||||
| 16 | 21 | i < n? | 6 | 4 | ||||||||||||
| 17 | 22 | Read arr[i] | 6 | 4 | 40 | |||||||||||
| 18 | 21 | i = i + 1 | 6 | 5 | ||||||||||||
| 19 | 21 | i < n? | 6 | 5 | ||||||||||||
| 20 | 22 | Read arr[i] | 6 | 5 | 56 |
Time and space complexity
Time: O(log n) · Space: O(log n). Each recursive call halves the search range, and the recursion depth is at most log n stack frames.
Common mistakes
- Using mid or mid without the -1/+1 (for example recursing on (low, mid)), which can cause infinite recursion because the range never shrinks.
- Running it on an unsorted array. Binary search only works if the numbers are in sorted order.
- Forgetting that the function returns a 0-based index, so main() must print result + 1 to show a human-friendly position.
Viva questions
Q1. What does the condition `low > high` on line 4 check, and why does it return -1?
It checks whether the search range has become empty, which means every possible position has been ruled out. So the key is not in the array and the function returns -1, since -1 can never be a valid index.
Q2. Why must the array be sorted for this program to work?
Binary search compares the key with the middle element and throws away one half. That is only correct if smaller values are on the left and larger on the right. On an unsorted array it can discard the half that contains the key.
Q3. What is the base case of this recursion, and are there more than one?
There are two stopping points: `low > high`, which returns -1 for not found, and `arr[mid] == key`, which returns mid for found. Without them the recursion would never end.
Q4. Why do we call binarySearch with `mid - 1` and `mid + 1` instead of just `mid`?
We have already compared arr[mid] with the key and it did not match, so mid can be excluded. Passing `mid` again could keep the same range forever and cause infinite recursion.
Q5. Why does main print `result + 1` instead of `result`?
The function returns a 0-based array index, but people count positions from 1. Adding 1 converts the index to a human-friendly position.
Q6. What happens if n is 0, or the array has only one element?
If n is 0, the call is binarySearch(arr, 0, -1, key). Here low > high at once, so it prints 'Key not found'. With one element, low = high = 0, so mid is 0, and it either matches or recurses into an empty range and returns -1.
Q7. What is the time complexity of this program, and what about the space used by recursion?
Time is O(log n), because each call halves the range, so at most about log2(n) + 1 calls are made. The recursion uses O(log n) stack space, one frame per call.
Q8. What would change if the array had duplicate keys, or if you wanted an iterative version?
With duplicates, it returns whichever matching index it hits first, not necessarily the first or last occurrence. To find the first one you would keep searching the left half after a match. An iterative version would use a while (low <= high) loop and update low or high instead of recursing, giving O(1) space.
Q9. Is `(low + high) / 2` always safe? How could you improve it?
For very large arrays, low + high can overflow an int, giving a wrong mid. A safer form is `low + (high - low) / 2`. For this program's array size of at most 100, it is fine.
Frequently asked questions
What is the base case in recursive binary search?
The base case is low > high, which means the search range is empty and the key is not in the array, so the function returns -1. The other stopping case is arr[mid] == key, where the index is returned.
What is the time complexity of recursive binary search?
It is O(log n), because each call halves the range being searched. It also uses O(log n) extra stack space for the recursive calls.
Why does the program print result + 1 instead of result?
binarySearch returns an array index, which starts at 0. Adding 1 converts it to a position counted from 1, so index 3 is printed as position 4.