Master Binary Search Recursive & Binary Search Iterative - 5 Leetcode Java Solutions

Binary Search is one of the most efficient searching algorithms widely used in computer science. Whether you are building applications, preparing for coding interviews, or solving algorithmic problems on platforms like Leetcode, understanding Binary Search is essential. In this article, we’ll explore the Binary Search Recursive and Binary Search Iterative approaches in Java, and dive into how Binary Search is commonly applied in Leetcode challenges.

Table of Contents

What is Binary Search?

Binary Search is an algorithm that efficiently locates a target element within a sorted array or list. It works by repeatedly dividing the search range in half, comparing the middle element to the target value, and discarding one-half of the list in each iteration. With a time complexity of O(log n), Binary Search is far superior to linear search for large datasets.

Also check: Sliding Window Algorithm – Fixed and Variable-Length Solutions

Binary Search Problem

As mentioned above, in a typical binary search problem you will be given a sorted array and an element that you need to find. This article covers both the solutions/ approaches for solving the binary search problem: Recursive & Iterative.

Leetcode Problem: Binary Search

Binary Search Recursive in Java

The recursive implementation of the Binary Search algorithm is a natural and elegant way to divide the problem. In the recursive approach, the algorithm calls itself on a smaller subarray until the target is found or the search range is exhausted. The function typically takes parameters like the array, left index, right index, and the target element to search.

Binary Search Recursive: Code Example in Java

Here’s an implementation of the Binary Search recursive approach in Java:

public class BinarySearch {

    // Binary Search Recursive Method
    public static int binarySearchRecursive(int[] arr, int left, int right, int target) {
        // Base case: if the search range is invalid
        if (left > right) {
            return -1;  // Target not found
        }
        
        // Find the middle element
        int mid = left + (right - left) / 2;
        
        // Check if the middle element is the target
        if (arr[mid] == target) {
            return mid;  // Target found
        }
        
        // If the target is smaller, search the left half
        if (arr[mid] > target) {
            return binarySearchRecursive(arr, left, mid - 1, target);
        }
        
        // If the target is larger, search the right half
        return binarySearchRecursive(arr, mid + 1, right, target);
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 13;
        int result = binarySearchRecursive(arr, 0, arr.length - 1, target);
        
        if (result == -1) {
            System.out.println("Element not found!");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Binary Search Recursive Iterative Leetcode Java

Explanation of the Binary Search Recursive Algorithm:

Base Case: If the left index exceeds the right index, we return -1 (indicating the target element was not found).
Middle Element Calculation: We calculate the middle index mid = left + (right – left) / 2 to avoid overflow.
Target Comparison:
- If the middle element equals the target, return the index mid.
- If the target is smaller than the middle element, recursively search in the left half (left to mid – 1).
- If the target is greater than the middle element, recursively search in the right half (mid + 1 to right).

Binary Search Iterative in Java

While the recursive approach is elegant, the iterative version of the Binary Search algorithm is often more efficient in terms of memory usage because it doesn’t require additional function calls. The logic remains the same, but instead of calling the function recursively, we use a loop to narrow down the search range.

Binary Search Iterative: Code Example in Java

Here’s how to implement the Binary Search iterative approach in Java:

public class BinarySearch {

    // Binary Search Iterative Method
    public static int binarySearchIterative(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // Find the middle element
            int mid = left + (right - left) / 2;
            
            // Check if the middle element is the target
            if (arr[mid] == target) {
                return mid;  // Target found
            }
            
            // If the target is smaller, search the left half
            if (arr[mid] > target) {
                right = mid - 1;
            }
            // If the target is larger, search the right half
            else {
                left = mid + 1;
            }
        }
        
        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 13;
        int result = binarySearchIterative(arr, target);
        
        if (result == -1) {
            System.out.println("Element not found!");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

You can refer the image from the Recursive Binary Search Algorithm example as the core logic and flow is the same.

Explanation of the Binary Search Iterative Algorithm:

The loop continues until the left index is greater than the right index, which indicates that the element is not present.
In each iteration, the middle element is calculated.
Based on the comparison between the target and middle element:
- If the middle element is equal to the target, return the index.
- If the target is smaller, adjust the right pointer to search the left half.
- If the target is larger, adjust the left pointer to search the right half.

Also check: Greedy Algorithm: A Comprehensive Guide With Examples

Binary Search on Leetcode: Practical Applications

Leetcode is one of the best platforms for practicing algorithms, and Binary Search frequently appears in problems that require efficient searching or range queries. By leveraging Binary Search Recursive or Binary Search Iterative, you can solve problems that would otherwise be inefficient or require brute force, especially when dealing with large datasets. Below are some examples of how Binary Search is applied to various types of problems on Leetcode.

1. Search in Rotated Sorted Array – Binary Search Iterative Leetcode Solution

Problem: Given a rotated sorted array, you need to find the target element’s index. A rotated sorted array is an array that has been shifted at some pivot index.

Leetcode Problem: Search in Rotated Sorted Array

Solution Strategy:

Binary Search Iterative is applied, but since the array is rotated, we need to account for the fact that the middle element might not always be in the sorted half.
We check whether the left or right half is sorted and adjust the search direction accordingly.

Code Example:

public class BinarySearch {

    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 which side is sorted
            if (nums[left] <= nums[mid]) {
                // Left side is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;  // Search left
                } else {
                    left = mid + 1;   // Search right
                }
            } else {
                // Right side is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;  // Search right
                } else {
                    right = mid - 1; // Search left
                }
            }
        }
        
        return -1;  // Target not found
    }

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

Explanation:

We first check whether the middle element is equal to the target.
Then, we determine which half of the array is sorted. If the left side is sorted, we check if the target lies within the range of the left half. If it does, we search the left half; otherwise, we search the right half. The same logic is applied when the right half is sorted.

2. Find First and Last Position of an Element in a Sorted Array – Binary Search Iterative Leetcode Solution

Problem: Given a sorted array, you need to find the first and last position of a given target element. If the target is not found, return [-1, -1].

Leetcode Problem: Find First and Last Position of Element in Sorted Array

Solution Strategy:

The idea is to use Binary Search Iterative to find the first occurrence of the target, and then use Binary Search Iterative again to find the last occurrence. This ensures that we efficiently locate both positions in O(log n) time.

Code Example:

public class BinarySearch {

    public static int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = findFirst(nums, target);
        result[1] = findLast(nums, target);
        return result;
    }
    
    // Find the first position of the target
    private static int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1, firstPos = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                firstPos = mid;
                right = mid - 1;  // Search left half
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return firstPos;
    }
    
    // Find the last position of the target
    private static int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1, lastPos = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                lastPos = mid;
                left = mid + 1;  // Search right half
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return lastPos;
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] result = searchRange(nums, target);
        
        System.out.println("First and Last positions: [" + result[0] + ", " + result[1] + "]");
    }
}

Explanation:

We first use Binary Search Iterative to find the first occurrence by adjusting the search space to the left after finding the target.
Next, we use Binary Search Iterative to find the last occurrence by adjusting the search space to the right after finding the target.
Both operations have a time complexity of O(log n), ensuring efficiency.

3. Find Minimum in Rotated Sorted Array – Binary Search Recursive Leetcode Solution

Problem: You are given a rotated sorted array. You need to find the minimum element in the array. It’s assumed that the array does not contain duplicates.

Leetcode Problem: Find Minimum in Rotated Sorted Array

Solution Strategy:

The key observation in a rotated sorted array is that the array can be divided into two subarrays: one that is sorted and the other that is rotated.
Binary Search Recursive can be used to find the minimum efficiently by comparing the middle element with the rightmost element.
If the middle element is greater than the rightmost element, it means the minimum is on the right side of the array (including the middle element).
If the middle element is smaller than or equal to the rightmost element, it indicates that the minimum lies on the left side of the array (including the middle element).

Code Example:

public class BinarySearch {

    // Recursive Binary Search to find the minimum in a rotated sorted array
    public static int findMin(int[] nums, int left, int right) {
        // Base case: when left and right are the same, we've found the minimum element
        if (left == right) {
            return nums[left];
        }
        
        int mid = left + (right - left) / 2;
        
        // If the middle element is greater than the rightmost element, 
        // then the minimum is in the right half
        if (nums[mid] > nums[right]) {
            return findMin(nums, mid + 1, right);
        } else {
            // If the middle element is smaller than or equal to the rightmost element,
            // then the minimum is in the left half (including mid)
            return findMin(nums, left, mid);
        }
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int result = findMin(nums, 0, nums.length - 1);
        
        System.out.println("The minimum element is: " + result);
    }
}

Explanation:

Base Case: The recursion ends when left == right, indicating that we have narrowed down the search to a single element. This element is the minimum, as there are no more elements left to check.
Mid Calculation: We calculate the middle index with mid = left + (right – left) / 2 to avoid overflow issues, especially when the left and right values are large.
Recursive Search:
- If nums[mid] > nums[right], it means the minimum value lies in the right half of the array, so we recursively call findMin(nums, mid + 1, right).
- If nums[mid] <= nums[right], the minimum value is either at mid or in the left half. Therefore, we recursively call findMin(nums, left, mid).
The recursion continues until we find the smallest element in the rotated array.

4. Square Root of a Number

Problem: Given a non-negative integer x, return the square root of x rounded down to the nearest integer. Implement the solution using Binary Search.

Leetcode Problem: Sqrt(x)

Solution Strategy:

We can apply Binary Search Iterative on the range [0, x] to find the square root. If the square of the middle value is equal to x, we’ve found the square root. If it’s greater, we adjust the search to the left half; otherwise, we search the right half.

Code Example:

public class BinarySearch {

    public static int mySqrt(int x) {
        int left = 0, right = x;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long midSquared = (long) mid * mid;
            
            if (midSquared == x) {
                return mid;  // Exact square root found
            } else if (midSquared > x) {
                right = mid - 1;  // Search the left half
            } else {
                left = mid + 1;   // Search the right half
            }
        }
        
        return right;  // When left exceeds right, right will be the floor value
    }

    public static void main(String[] args) {
        int x = 8;
        System.out.println("Square root of " + x + " is: " + mySqrt(x));
    }
}

Explanation:

We use Binary Search on the range [0, x] to find the largest integer whose square is less than or equal to x.
The condition mid * mid == x checks if we’ve found the exact square root.

Recursive Binary Search vs Iterative Binary Search: When to Use Which?

Both recursive and iterative approaches to the Binary Search algorithm have their advantages and trade-offs.

Recursive Binary Search:
- Pros: The code is clean, elegant, and easy to understand. It is a direct implementation of the divide-and-conquer technique.
- Cons: It involves function calls, which can lead to stack overflow errors for very large arrays. It also uses more memory due to the recursion stack.
Iterative Binary Search:
- Pros: More memory efficient since it doesn’t require recursion. It is usually faster in practice due to the lack of function call overhead.
- Cons: Slightly more complex to write and less intuitive than the recursive version.

Conclusion

Binary Search is an indispensable tool for solving a wide range of problems efficiently. Whether you choose the recursive or iterative approach depends on the problem at hand and the constraints of your environment. On platforms like Leetcode, Binary Search is frequently used in problems involving sorted arrays, rotations, or range queries. Mastering both versions and understanding when to use each is key to becoming proficient in algorithms and acing coding interviews.

By practicing both Binary Search Recursive and Binary Search Iterative approaches in Java, you’ll be well-prepared to tackle Leetcode challenges and other algorithmic problems that require efficient searching techniques.

With this guide, you now have a deeper understanding of Binary Search and can confidently approach problems in both recursive and iterative forms, including those found in Leetcode.

That’s all on the Binary Search Recursion algorithm and the Binary Search Iterative algorithm.

To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.

Please follow us on Medium.