Start learning free

LESSON 278 OF 409 · DIVIDE AND CONQUER

Binary Search II in C++ with 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

    C++ · DIVIDE AND CONQUER

    Binary Search in C++, 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) that searches for the value in the subarray nums[left...right].
    2. Compute the middle index mid and compare nums[mid] to the target value.
    3. If nums[mid] is equal to the value, return mid.
    4. If nums[mid] is less than the value, search in the right subarray nums[mid + 1...right].
    5. If nums[mid] is greater than the 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. Initialize the search with the entire array: binarySearch(nums, 0, nums.size() - 1).
    2. In each recursive call, compute the middle index: mid = left + (right - left) / 2.
    3. 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.
    4. 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:

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