Start learning free

LESSON 279 OF 410 · DIVIDE AND CONQUER

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

Practice Recursive Read the full explanation

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: the element at index 2 is 4

Note:

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

Hints:

Since our subproblems reduce to searching the value in a subarray, we will write a recursive helper function which takes nums, the bounds left and right and value, looks for value in the part of nums between indexes left and right (both included) and returns its index or -1 if not found.

Inside the function, we should compute the middle index mid and compare the element at mid to value. What should we do if:
  • the element at mid is equal to value?
  • the element at mid is less than value?
  • the element at mid is greater than value?

  • If the element at mid is equal to value, then we found our solution and we should return mid
  • If the element at mid is less than value, we should continue the search between indexes mid + 1 and right, i.e. return the result of the recursive call on that range
  • If the element at mid is greater than value, we should continue the search between indexes left and mid - 1, i.e. return the result of the recursive call on that range
When should the function return -1 tho?

At the start of the function, we should treat the base case: left > right. This means we reduced the searching area to an empty subarray, so there is no solution and we should return -1
STEP 1 OF 7
    Ctrl + Enter to check

    JAVA · DIVIDE AND CONQUER

    Binary Search in Java, explained

    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:

    1. Define a recursive function binarySearch(nums, left, right, value) that searches for value in the subarray nums[left...right].
    2. Compute the middle index mid and compare nums[mid] to value.
    3. If nums[mid] is equal to value, return mid.
    4. If nums[mid] is less than value, search in the right subarray nums[mid + 1...right].
    5. If nums[mid] is greater than value, search in the left subarray nums[left...mid - 1].
    6. 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:

    1. Check the base case: if left > right, return -1.
    2. Compute the middle index: mid = left + (right - left) / 2.
    3. 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:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free