Solution Binary Search

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.

Code

Here is the code for this algorithm:

public class Solution {

  public static boolean binarySearch(int[] nums, int target) {
    return binarySearchHelper(nums, target, 0, nums.length - 1);
  }

  private static boolean binarySearchHelper(
    int[] nums,
    int target,
    int low,
    int high
  ) {
    if (low > high) {
      return false; // Base case: key not found
    }

    int mid = low + (high - low) / 2;
    if (nums[mid] == target) {
      return true; // Base case: key found
    } else if (nums[mid] > target) {
      return binarySearchHelper(nums, target, low, mid - 1); // Recursive call on left half
    } else {
      return binarySearchHelper(nums, target, mid + 1, high); // Recursive call on right half
    }
  }

  public static void main(String[] args) {
    // Example inputs
    int[][] examples = {
      { 1, 2, 3, 4, 5 },
      { 2, 4, 6, 8, 10 },
      { 3, 6, 9, 12, 15 },
    };
    int[] keys = { 4, 5, 15 };

    for (int i = 0; i < examples.length; i++) {
      int[] nums = examples[i];
      int target = keys[i];
      boolean result = binarySearch(nums, target);
      System.out.println(
        "Example " + (i + 1) + ": " + target + " found? " + result
      );
    }
  }
}

Time and Space Complexity

The time complexity of the binary search algorithm is as the search space is halved at each recursive step. The space complexity is as well, considering the recursive function calls stored on the call stack.

I'm working on the problem **Solution Binary Search** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Solution Binary Search** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Solution Binary Search**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Solution Binary Search**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.