Binary Search: Iterative vs Recursive

You already know binary search finds a number in a sorted list fast. But when you sit down to write it, you have a choice to make. Do you use a loop? Or do you make the function call itself? Both work. Both are correct. The thing is, they use a slightly different amount of memory. So let’s write both. We’ll run both. Then you’ll see exactly when to pick one over the other.

🎯 The Problem We’re Solving

Say you have a sorted array. You want to find where a number sits. Binary search keeps cutting the search range in half until it lands on the answer. That halving is the smart part.

But the “keep cutting in half” idea can be coded in two shapes:

• One way uses a loop that updates two pointers again and again. We call this iterative. It means the code repeats the work using a loop.
• The other way makes the function call itself on the smaller half each time. We call this recursive. It means the function calls itself to solve a smaller piece of the same problem.

The pain point is simple. Beginners often learn only one shape. Then they freeze in an interview when asked for the other. So we’ll learn both today. After this, you’ll never freeze.

🧠 A Quick Real-World Picture

Think about looking for a name in a thick phone book. You open the middle. The name you want comes before that page. So you tear the book in half and keep only the left part. Then you open the middle of that part. You keep doing this.

• The iterative way is like keeping the same book in your hands. You just move your two thumbs closer each time.
• The recursive way is like handing the smaller half to a friend and saying “you search this one.” That friend hands an even smaller half to another friend. And so on.

Same idea. The recursive way just keeps passing the job along. Each friend remembers where they were. That “remembering” is what costs a little extra memory. Keep that in mind.

🔁 How the Iterative Version Works

The iterative version keeps two markers. One marks the start of the range, called low. One marks the end of the range, called high. Then a loop runs while the range is still valid.

Here is what happens on each pass of the loop:

• Find the middle index with mid = low + (high - low) / 2. We write it this way so the numbers don’t get too big and overflow.
• If the value at mid is the target, we found it. Return mid.
• If the value at mid is less than the target, the answer must be on the right side. So move low to mid + 1.
• If the value at mid is greater than the target, the answer must be on the left side. So move high to mid - 1.

When low goes past high, the range is empty. The number is not there. So we return -1.

Steps to write iterative binary search:

1. Set low = 0 and high = n - 1.
2. Loop while low <= high.
3. Compute mid = low + (high - low) / 2.
4. If arr[mid] == target, return mid.
5. If arr[mid] < target, set low = mid + 1.
6. Else set high = mid - 1.
7. If the loop ends with no match, return -1.

🌀 How the Recursive Version Works

The recursive version does the same halving. But instead of a loop, it calls itself with a smaller range. We pass low and high into the function. Each call checks the middle. Then it calls itself again on either the left half or the right half.

Every recursive function needs a base case. That is the condition that stops the calls so they don’t go on forever. Here the base case is low > high. That means the range is empty. So we return -1.

Steps to write recursive binary search:

1. The function takes arr, low, high, and target.
2. Base case: if low > high, return -1.
3. Compute mid = low + (high - low) / 2.
4. If arr[mid] == target, return mid.
5. If arr[mid] < target, call the function again with low = mid + 1.
6. Else call the function again with high = mid - 1.

The first call starts with low = 0 and high = n - 1. Just like before.

💻 Both Versions in Code

Each tab below shows the iterative version first. Then it shows the recursive version. We search for the number 23 in a sorted array.

#include <stdio.h>

// Iterative: uses a loop and two markers
int searchIterative(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // middle, overflow-safe
        if (arr[mid] == target) return mid; // found it
        if (arr[mid] < target) low = mid + 1;  // go right
        else high = mid - 1;                    // go left
    }
    return -1; // not found
}

// Recursive: the function calls itself on the smaller half
int searchRecursive(int arr[], int low, int high, int target) {
    if (low > high) return -1;              // base case: empty range
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)
        return searchRecursive(arr, mid + 1, high, target); // right half
    return searchRecursive(arr, low, mid - 1, target);      // left half
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Iterative found 23 at index: %d\n", searchIterative(arr, n, 23));
    printf("Recursive found 23 at index: %d\n", searchRecursive(arr, 0, n - 1, 23));
    return 0;
}

Iterative found 23 at index: 5
Recursive found 23 at index: 5

#include <iostream>
using namespace std;

// Iterative: uses a loop and two markers
int searchIterative(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // middle, overflow-safe
        if (arr[mid] == target) return mid; // found it
        if (arr[mid] < target) low = mid + 1;  // go right
        else high = mid - 1;                    // go left
    }
    return -1; // not found
}

// Recursive: the function calls itself on the smaller half
int searchRecursive(int arr[], int low, int high, int target) {
    if (low > high) return -1;              // base case: empty range
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)
        return searchRecursive(arr, mid + 1, high, target); // right half
    return searchRecursive(arr, low, mid - 1, target);      // left half
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Iterative found 23 at index: " << searchIterative(arr, n, 23) << endl;
    cout << "Recursive found 23 at index: " << searchRecursive(arr, 0, n - 1, 23) << endl;
    return 0;
}

Iterative found 23 at index: 5
Recursive found 23 at index: 5

public class BinarySearch {

    // Iterative: uses a loop and two markers
    static int searchIterative(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;   // middle, overflow-safe
            if (arr[mid] == target) return mid; // found it
            if (arr[mid] < target) low = mid + 1;  // go right
            else high = mid - 1;                    // go left
        }
        return -1; // not found
    }

    // Recursive: the function calls itself on the smaller half
    static int searchRecursive(int[] arr, int low, int high, int target) {
        if (low > high) return -1;              // base case: empty range
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target)
            return searchRecursive(arr, mid + 1, high, target); // right half
        return searchRecursive(arr, low, mid - 1, target);      // left half
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

        System.out.println("Iterative found 23 at index: " + searchIterative(arr, 23));
        System.out.println("Recursive found 23 at index: " + searchRecursive(arr, 0, arr.length - 1, 23));
    }
}

Iterative found 23 at index: 5
Recursive found 23 at index: 5

# Iterative: uses a loop and two markers
def search_iterative(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2     # middle, overflow-safe
        if arr[mid] == target:
            return mid                    # found it
        if arr[mid] < target:
            low = mid + 1                 # go right
        else:
            high = mid - 1                # go left
    return -1                             # not found

# Recursive: the function calls itself on the smaller half
def search_recursive(arr, low, high, target):
    if low > high:                        # base case: empty range
        return -1
    mid = low + (high - low) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return search_recursive(arr, mid + 1, high, target)  # right half
    return search_recursive(arr, low, mid - 1, target)       # left half

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

print("Iterative found 23 at index:", search_iterative(arr, 23))
print("Recursive found 23 at index:", search_recursive(arr, 0, len(arr) - 1, 23))

Iterative found 23 at index: 5
Recursive found 23 at index: 5

// Iterative: uses a loop and two markers
function searchIterative(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2); // middle, overflow-safe
    if (arr[mid] === target) return mid;            // found it
    if (arr[mid] < target) low = mid + 1;           // go right
    else high = mid - 1;                            // go left
  }
  return -1; // not found
}

// Recursive: the function calls itself on the smaller half
function searchRecursive(arr, low, high, target) {
  if (low > high) return -1;                        // base case: empty range
  const mid = low + Math.floor((high - low) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target)
    return searchRecursive(arr, mid + 1, high, target); // right half
  return searchRecursive(arr, low, mid - 1, target);    // left half
}

const arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

console.log("Iterative found 23 at index:", searchIterative(arr, 23));
console.log("Recursive found 23 at index:", searchRecursive(arr, 0, arr.length - 1, 23));

Iterative found 23 at index: 5
Recursive found 23 at index: 5

⚖️ The Real Trade-off: Memory

Here is the part most beginners miss. Both versions take O(log n) time. That is because both cut the range in half each step. Time is a tie. The difference is space.

Let me show you what happens to memory in each one:

• The iterative version uses the same two variables the whole time, just low and high. So its extra memory stays fixed no matter how big the array is. That is O(1) space. It means constant extra memory.
• The recursive version makes a new function call for each halving step. Each call waits for the one inside it to finish. The computer stacks these waiting calls in memory. That stack of waiting calls is called the call stack. With about log n halvings, you get about log n calls waiting. That is O(log n) space.

So the picture is:

• Recursive reads cleaner. It matches the “divide and conquer” idea word for word.
• Iterative uses less memory. It never risks the call stack getting too deep.

📊 Iterative vs Recursive at a Glance

Here is the side-by-side so you can see both at once.

⚠️ Common Mistakes to Avoid

A few slips trip up almost everyone the first time. Watch for these:

• Writing (low + high) / 2 instead of low + (high - low) / 2. On big arrays the first one can overflow. Use the safe form.
• Forgetting the base case in the recursive version. With no low > high check, the function keeps calling itself and crashes.
• Using low < high instead of low <= high in the loop. With < you miss the case where the target sits at the last single spot.
• Setting low = mid or high = mid instead of mid + 1 and mid - 1. That leaves mid in the range again and the loop runs forever.
• Running binary search on an array that is not sorted. Binary search only works on sorted data, so sort it first.

🧩 What You’ve Learned

✅ Binary search can be written two ways: iterative with a loop, or recursive where the function calls itself.

✅ Both take O(log n) time because both cut the search range in half each step.

✅ The iterative version uses O(1) extra space, just low and high.

✅ The recursive version uses O(log n) space because each call waits on the call stack.

✅ Always use the overflow-safe middle low + (high - low) / 2, keep a base case in recursion, and only search sorted data.

🚀 What’s Next?

• Binary Search
• Recursion