Binary Search II in C++ with 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) that searches for the value in the subarray nums[left...right].
Compute the middle index mid and compare nums[mid] to the target value.
If nums[mid] is equal to the value, return mid.
If nums[mid] is less than the value, search in the right subarray nums[mid + 1...right].
If nums[mid] is greater than the 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:

Initialize the search with the entire array: binarySearch(nums, 0, nums.size() - 1).
In each recursive call, compute the middle index: mid = left + (right - left) / 2.
Compare nums[mid] with the target value:
- If nums[mid] is equal to the value, return mid.
- If nums[mid] is less than the value, search in the right subarray.
- If nums[mid] is greater than the value, search in the left subarray.
If the search interval becomes invalid (i.e., left > right), return -1.

Code Implementation


#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int left, int right, int value) {
    // Base case: if the search interval is invalid
    if (left > right) {
        return -1;
    }

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

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

int main() {
    std::vector<int> nums = {1, 2, 4, 5};
    int value = 4;
    int result = binarySearch(nums, 0, nums.size() - 1, value);
    std::cout << "Index of " << value << " is: " << result << std::endl;
    return 0;
}

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 single element is the target 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:

Basic cases with small arrays.
Edge cases with empty arrays and single-element arrays.
Cases where the value is not present in the array.
Cases with large arrays to ensure the algorithm handles them efficiently.

Testing frameworks like Google Test can be used to automate and manage test cases.

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 how to handle it correctly.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the recursive Binary Search algorithm, its implementation in C++, and its complexity analysis. Understanding and solving such problems is crucial for developing efficient algorithms and improving problem-solving skills. Practice and exploration of further problems are encouraged.

Additional Resources

For further reading and practice, consider the following resources: