Java Program for Binary Search Using Recursion

A Java program for binary search using recursion calls a method like binarySearch(arr, low, high, key) that checks the middle element and recursively searches the left or right half until the key is found or the range is empty.

Examples

Inputarr = {1, 3, 5, 7, 9}, key = 7

OutputKey found at index 3

Inputarr = {2, 4, 6, 8, 10}, key = 5

OutputKey not found

Inputarr = {10}, key = 10

OutputKey found at index 0

How to Think About It

To do a binary search with recursion, first find the middle of the current array range. If the middle element is the key, return its index. If the key is smaller, search the left half by calling the function again with the left range. If the key is larger, search the right half similarly. Stop when the range is empty.

Algorithm

1

Start with the full array range from low to high indexes.

2

Find the middle index between low and high.

3

If the middle element equals the key, return the middle index.

4

If the key is less than the middle element, recursively search the left half.

5

If the key is greater than the middle element, recursively search the right half.

6

If low exceeds high, return -1 to indicate the key is not found.

Code

java

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int low, int high, int key) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 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) {
        int[] arr = {1, 3, 5, 7, 9};
        int key = 7;
        int result = binarySearch(arr, 0, arr.length - 1, key);
        if (result == -1) {
            System.out.println("Key not found");
        } else {
            System.out.println("Key found at index " + result);
        }
    }
}

Output

Key found at index 3

Dry Run

Let's trace searching for key 7 in array {1, 3, 5, 7, 9} using recursion.

1

Initial call

low=0, high=4, mid=2, arr[mid]=5, key=7; key > arr[mid], search right half

2

Second call

low=3, high=4, mid=3, arr[mid]=7, key=7; key == arr[mid], return 3

Call	low	high	mid	arr[mid]	key	Action
1	0	4	2	5	7	key > arr[mid], search right half
2	3	4	3	7	7	key == arr[mid], return index 3

Why This Works

Step 1: Divide the array

The code finds the middle index using mid = low + (high - low) / 2 to avoid overflow and splits the array into halves.

Step 2: Compare middle element

It compares the middle element with the key using arr[mid] == key to check if the search is successful.

Step 3: Recursive search

If the key is smaller or larger, it calls itself recursively on the left or right half using binarySearch(arr, low, mid - 1, key) or binarySearch(arr, mid + 1, high, key).

Step 4: Stop condition

When low > high, it means the key is not in the array, so it returns -1.

Alternative Approaches

Iterative binary search

java

public class BinarySearchIterative {
    public static int binarySearch(int[] arr, int key) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == key) return mid;
            else if (key < arr[mid]) high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int key = 7;
        int result = binarySearch(arr, key);
        if (result == -1) System.out.println("Key not found");
        else System.out.println("Key found at index " + result);
    }
}

Uses a loop instead of recursion, which can be more memory efficient and avoids stack overflow.

Using Java Arrays binarySearch method

java

import java.util.Arrays;
public class BinarySearchBuiltIn {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int key = 7;
        int result = Arrays.binarySearch(arr, key);
        if (result < 0) System.out.println("Key not found");
        else System.out.println("Key found at index " + result);
    }
}

Uses Java's built-in method which is optimized and simple but does not show recursion.

Complexity: O(log n) time, O(log n) space

Time Complexity

Binary search divides the array in half each time, so it runs in logarithmic time O(log n).

Space Complexity

Recursive calls add to the call stack, so space complexity is O(log n) due to recursion depth.

Which Approach is Fastest?

Iterative binary search uses O(1) space and is faster in practice due to no recursion overhead.

Approach	Time	Space	Best For
Recursive binary search	O(log n)	O(log n)	Learning recursion and divide-and-conquer
Iterative binary search	O(log n)	O(1)	Memory-efficient and practical use
Java built-in Arrays.binarySearch	O(log n)	O(1)	Quick and optimized search without manual code