Recursive Binary Search Implementation in Java

Binary search is a highly efficient searching algorithm that works on sorted arrays. It repeatedly divides the search interval in half. This document details a recursive implementation of binary search in Java, with considerations for its use in competitive programming.

Explanation of Recursive Binary Search

The recursive binary search algorithm works as follows:

1. Base Cases:
   • If the search interval is empty (i.e., left > right), the element is not found, and we return -1.
   • If the middle element is equal to the target value, we return the index of the middle element.
2. Recursive Step:
   • If the target value is less than the middle element, we recursively search the left half of the array.
   • If the target value is greater than the middle element, we recursively search the right half of the array.

Implementing Binary Search Using Recursion in Java

Code Example

 public class RecursiveBinarySearch {

    public static int binarySearch(int[] arr, int target, int left, int right) {
        // Base Case 1: Element not found
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2; // Prevents potential integer overflow

        // Base Case 2: Element found
        if (arr[mid] == target) {
            return mid;
        }

        // Recursive Step: Search left half
        if (target < arr[mid]) {
            return binarySearch(arr, target, left, mid - 1);
        }

        // Recursive Step: Search right half
        else {
            return binarySearch(arr, target, mid + 1, right);
        }
    }

    public static int binarySearch(int[] arr, int target) {
        return binarySearch(arr, target, 0, arr.length - 1);
    }


    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int target = 10;
        int result = binarySearch(arr, target);
        if (result == -1)
            System.out.println("Element is not found");
        else
            System.out.println("Element is found at index: " + result);
    }
} 

Base Cases

The base cases are crucial for stopping the recursion. Without them, the algorithm would run indefinitely, leading to a stack overflow error. In this implementation, the base cases are:

• left > right: This condition indicates that the target element is not present in the array. The search space has been exhausted.
• arr[mid] == target: This condition indicates that the target element has been found at index mid.

Recursive Calls

The recursive calls are made to narrow down the search space. Each call reduces the search space by half. The recursive calls are:

• binarySearch(arr, target, left, mid - 1): Searches the left half of the array if the target is less than the middle element.
• binarySearch(arr, target, mid + 1, right): Searches the right half of the array if the target is greater than the middle element.

Potential Stack Overflow Issues

Recursive implementations can lead to stack overflow errors, especially with large input sizes. This is because each recursive call adds a new frame to the call stack. The depth of the recursion (number of calls) is proportional to log2(n) where 'n' is the size of the array. While the logarithmic depth mitigates the risk, it's still a concern for very large datasets or deeply nested recursion elsewhere in the program. In competitive programming, it's often safer and more performant to use an iterative binary search to avoid stack overflow and potentially gain a slight performance advantage. You can increase the stack size using JVM options (e.g., -Xss), but this is often discouraged in competitive environments. Choose iterative solutions whenever possible.

Binary Search in Competitive Programming in Java with Solutions

Binary search is a fundamental algorithm in competitive programming. Its logarithmic time complexity (O(log n)) makes it ideal for searching large datasets quickly. Below are some common scenarios where binary search is used, along with solutions.

Problem 1: Finding the First Occurrence of an Element

Given a sorted array and a target value, find the index of the *first* occurrence of the target value. If the target value is not present, return -1.

 public class FirstOccurrence {

    public static int findFirstOccurrence(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                result = mid; // Found, but check for earlier occurrences
                right = mid - 1; // Continue searching the left half
            } else if (target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result;
    }


    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 4, 4, 10, 40};
        int target = 4;
        int result = findFirstOccurrence(arr, target);
        if (result == -1)
            System.out.println("Element is not found");
        else
            System.out.println("First occurrence is at index: " + result);
    }
} 

Problem 2: Finding the Last Occurrence of an Element

Given a sorted array and a target value, find the index of the *last* occurrence of the target value. If the target value is not present, return -1.

 public class LastOccurrence {

    public static int findLastOccurrence(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                result = mid; // Found, but check for later occurrences
                left = mid + 1; // Continue searching the right half
            } else if (target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 4, 4, 10, 40};
        int target = 4;
        int result = findLastOccurrence(arr, target);
        if (result == -1)
            System.out.println("Element is not found");
        else
            System.out.println("Last occurrence is at index: " + result);
    }
} 

Problem 3: Search in a Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of O(log n).

 public class RotatedArraySearch {

    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // Check if left half is sorted
            if (nums[left] <= nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1; // Target is in the sorted left half
                } else {
                    left = mid + 1; // Target is in the unsorted right half
                }
            } else { // Right half is sorted
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1; // Target is in the sorted right half
                } else {
                    right = mid - 1; // Target is in the unsorted left half
                }
            }
        }

        return -1; // Target not found
    }


    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int result = search(arr, target);
        if (result == -1)
            System.out.println("Element is not found");
        else
            System.out.println("Element is found at index: " + result);
    }
}