Problem Statement

Write Recursive Approach to Implement Binary Search Algorithm.

The problem is to implement the binary search algorithm using recursion. Given a sorted array and a target key, the algorithm should determine whether the key is present in the array or not.

Examples

Constraints:

• 1 <= nums.length <= 10⁴
• -10⁴ < nums[i], target < 10⁴
• All the integers in nums are unique.
• nums is sorted in ascending order.

Solution

The algorithm follows a recursive approach to implement binary search. Here are the key points:

1. Base Case: If the lower bound is greater than the upper bound, return False as the key is not found.
2. Recursive Case:
   • Calculate the mid index between the lower and upper bounds.
   • Compare the element at the mid index with the target key.
     • If they are equal, return True as the key is found.
     • If the element at the mid index is greater than the target key, make a recursive call on the left half of the array with an updated upper bound of mid - 1.
     • If the element at the mid index is less than the target key, make a recursive call on the right half of the array with an updated lower bound of mid + 1.

The algorithm follows the principles of binary search, narrowing down the search space by half at each step. By utilizing recursion, it divides the array into smaller halves until the target key is found or the bounds become invalid.