Binary Search using recursion

Hello everyone my name is Sreejit Sengupta and I am currently pursuing my Bachelor's in Information Technology. I have been lately working with HTML, CSS, JavaScript and Java and today I will be writing on how to perform Binary Search using Recursion.

What is Binary Searching?

Binary search is an efficient algorithm for finding an item from a sorted array of items. It works by repeatedly dividing in half the portion of the array that could contain the item, until you've narrowed down the possible locations to just one.

Here is the basic procedure for performing a binary search:

Set a lower bound (start) and an upper bound (end) for the portion of the array that you want to search. The initial lower bound is usually 0, and the initial upper bound is the length of the array minus 1.
Calculate the middle point (mid) of the current search range by taking the average of the lower and upper bounds: mid = start + (end - start) / 2.
If the item at mid is the one you're looking for, return mid.
If the item at mid is greater than the item you're looking for, set end to mid - 1 and go back to step 2.
If the item at mid is less than the item you're looking for, set start to mid + 1 and go back to step 2.
If start is greater than end, the item is not in the list and you can return -1 or some other value indicating that the item was not found.

It has a Time Complexity of O(log n).

static int binarySearch (int[] arr, int target) {
        int start = 0; // Start position of search space.
        int end = arr.length - 1; // End position of search space.

        boolean isAscending = arr[start] < arr[end]; // Checking the manner in which the array is sorted.

        /* Algorithm for Binary Search */
        while (start <= end) {
            int mid = start + (end - start)/2;
            if (target == arr[mid]) {
                return mid;
            }

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
             }
        }
        return -1;
    }

What is Recursion?

Recursion is a programming technique in which a function calls itself with modified arguments. Recursion can be a powerful tool for solving problems, but it is important to ensure that the base case is properly defined, otherwise the function may end up calling itself indefinitely, leading to an infinite loop. It is also important to consider the efficiency of recursive solutions, as they can sometimes be slower than iterative solutions due to the overhead of repeatedly calling the function.

Here is a simple example of Recursion: Printing numbers from 1 to 5.

static void print(int n) {
        // Base Condition
        if (n > 5) {
            return;
        }
        System.out.println(n);
        print(n + 1);
    }

First, we pass 1 as the argument in the function. It checks for the base condition if it's true then it returns the function. Else it prints 'n' and passes 'n + 1' to itself.

main method calls print(1)
print(1) prints '1' and calls print(2)
print(2) prints '2' and calls print(3)
print(3) prints '3' and calls print(4)
print(4) prints '4' and calls print(5)
print(5) prints '5' and calls print(6)
n > 5 base condition met function returns.

Recursive Binary Search

The approach remains the same, we divide the array in half and grab the middle element, if it's equal to the target we return the index. Else we get two cases -

target element > middle element: We reduce the search space to mid + 1 to end.
target element < middle element: We reduce the search space to start to mid - 1.

In Recursive method the base condition will be target = middle element. Else we will check for the other two cases and pass the required arguments to the function i.e. the array itself, the target and modified values of start and end according to the condition.

 static int binary(int[] arr, int target, int start, int end) {
        int mid = start + (end - start) / 2; // Midddle index

        // Base condition
        if (target == arr[mid]) {
            return mid;
        }

        // If target < middle element; end = mid - 1
        if (target < arr[mid]) {
            return binary(arr, target, start, mid - 1);
        }

        // If target > middle element; start = mid + 1.
        return binary(arr, target, mid + 1, end);
    }

Let's say our Array is [1, 2, 3, 4, 5], target = 4, start = 0, end = array.length - 1;

The main method calls the function 'binary' with the above-mentioned arguments. Mid = 2 (start = 0 & end = 4)
Element at the middle is not equal to the target hence base condition is not met, now recursive call triggers, it passes the array, the target the modifies value of start i.e. mid + 1 as the target > middle element.
Mid = 3. Target = middle element, base condition met the second recursive calls returns from where it was called.
function 'binary' returns it's value to the main function.
Program over.

Thank you for reading my blog post! I hope that you found the information useful and informative. If you have any questions or comments, please don't hesitate to reach out. I would love to hear from you and continue the conversation. Be sure to check out our other blog posts for more interesting and informative content. Thanks again for stopping by!

Here is the link to my Twitter.

Binary Searching in Java using Recursion

What is Binary Searching?

What is Recursion?

Recursive Binary Search