Binary Search II in Java (O(log n) Time Complexity)

Implement a recursive Binary Search algorithm that given a sorted array of integers nums, finds and returns the index of a given value.

If the value doesn't exist in nums, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(log n) time and use O(log n) extra space.

Understanding the Problem

The core challenge of this problem is to efficiently find the index of a given value in a sorted array using a recursive approach. Binary Search is a classic algorithm that divides the search interval in half repeatedly, making it highly efficient for sorted arrays.

Common applications of Binary Search include searching in databases, finding elements in sorted data structures, and solving algorithmic problems that require efficient search operations.

Potential pitfalls include not handling the base case correctly, which can lead to infinite recursion or incorrect results.

Approach

To solve this problem, we can use the following approach:

Define a recursive function binarySearch(nums, left, right, value) that searches for value in the subarray nums[left...right].
Compute the middle index mid and compare nums[mid] to value.
If nums[mid] is equal to value, return mid.
If nums[mid] is less than value, search in the right subarray nums[mid + 1...right].
If nums[mid] is greater than value, search in the left subarray nums[left...mid - 1].
If left exceeds right, return -1 as the value is not present in the array.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Check the base case: if left > right, return -1.
Compute the middle index: mid = left + (right - left) / 2.
Compare nums[mid] with value:
- If nums[mid] == value, return mid.
- If nums[mid] < value, recursively search in the right subarray.
- If nums[mid] > value, recursively search in the left subarray.

Code Implementation

public class BinarySearch {
    // Recursive binary search function
    public static int binarySearch(int[] nums, int left, int right, int value) {
        // Base case: if left index exceeds right index, value is not present
        if (left > right) {
            return -1;
        }

        // Calculate the middle index
        int mid = left + (right - left) / 2;

        // Check if the middle element is the value we are searching for
        if (nums[mid] == value) {
            return mid;
        }

        // If the value is greater than the middle element, search in the right subarray
        if (nums[mid] < value) {
            return binarySearch(nums, mid + 1, right, value);
        }

        // If the value is less than the middle element, search in the left subarray
        return binarySearch(nums, left, mid - 1, value);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 5};
        int value = 4;
        int result = binarySearch(nums, 0, nums.length - 1, value);
        System.out.println("Index of " + value + ": " + result);
    }
}

Complexity Analysis

The time complexity of the recursive binary search algorithm is O(log n) because the search interval is halved in each recursive call.

The space complexity is also O(log n) due to the recursive call stack.

Edge Cases

Potential edge cases include:

Empty array: The function should return -1.
Value not present in the array: The function should return -1.
Array with one element: The function should correctly identify if the element is the value or not.

Examples:

Input: nums = [], value = 4
Output: -1

Input: nums = [1], value = 1
Output: 0

Input: nums = [1], value = 2
Output: -1

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small arrays.
Edge cases with empty arrays and single-element arrays.
Cases where the value is not present in the array.
Cases where the value is at the beginning, middle, or end of the array.

Example test cases:

int[] nums1 = {1, 2, 4, 5};
System.out.println(binarySearch(nums1, 0, nums1.length - 1, 4)); // Output: 2

int[] nums2 = {};
System.out.println(binarySearch(nums2, 0, nums2.length - 1, 4)); // Output: -1

int[] nums3 = {1};
System.out.println(binarySearch(nums3, 0, nums3.length - 1, 1)); // Output: 0

int[] nums4 = {1};
System.out.println(binarySearch(nums4, 0, nums4.length - 1, 2)); // Output: -1

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Break down the problem into smaller subproblems and solve them recursively.
Think about the base case and ensure it is handled correctly to avoid infinite recursion.
Practice solving similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed the recursive binary search algorithm, its implementation in Java, and its complexity analysis. Understanding and solving such problems is crucial for developing efficient algorithms and improving problem-solving skills.

We encourage you to practice and explore further to deepen your understanding of binary search and other algorithmic techniques.

Additional Resources

For further reading and practice problems, consider the following resources: