Binary Search Recursive Approach in DSA Java

Mental Model

Binary search splits a sorted list in half to find a target quickly by checking the middle element and deciding which half to search next.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is in the first or second half, and repeating this until you find it.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:     [0, 1, 2, 3, 4,  5,  6]
Pointers:    low=0 ↑       mid=3 ↑       high=6 ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], target: 9

Goal: Find the index of target 9 using recursive binary search

Step 1: Calculate mid index between low=0 and high=6, mid=3; compare array[mid]=7 with target=9

[1, 3, 5, 7, 9, 11, 13]
low=0 ↑ mid=3 (7) ↑ high=6 ↑

Why: Check middle element to decide which half to search next

Step 2: Since 7 < 9, search right half: low=4, high=6

[1, 3, 5, 7, 9, 11, 13]
low=4 ↑ high=6 ↑

Why: Target must be in right half because 9 is greater than 7

Step 3: Calculate mid index between low=4 and high=6, mid=5; compare array[mid]=11 with target=9

[1, 3, 5, 7, 9, 11, 13]
low=4 ↑ mid=5 (11) ↑ high=6 ↑

Why: Check middle element of new range to narrow search

Step 4: Since 11 > 9, search left half: low=4, high=4

[1, 3, 5, 7, 9, 11, 13]
low=4 ↑ high=4 ↑

Why: Target must be in left half because 9 is less than 11

Step 5: Calculate mid index between low=4 and high=4, mid=4; compare array[mid]=9 with target=9

[1, 3, 5, 7, 9, 11, 13]
low=4 ↑ mid=4 (9) ↑ high=4 ↑

Why: Check middle element which matches target

Step 6: Found target at index 4, return 4

[1, 3, 5, 7, 9, 11, 13]
Index found: 4

Why: Target found, end recursion

Result:

[1, 3, 5, 7, 9, 11, 13]
Target 9 found at index 4

Annotated Code

DSA Java

public class BinarySearchRecursive {

    public static int binarySearch(int[] arr, int target, int low, int high) {
        if (low > high) {
            return -1; // target not found
        }
        int mid = low + (high - low) / 2; // find middle index
        if (arr[mid] == target) {
            return mid; // target found
        } else if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, high); // search right half
        } else {
            return binarySearch(arr, target, low, mid - 1); // search left half
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13};
        int target = 9;
        int result = binarySearch(array, target, 0, array.length - 1);
        if (result == -1) {
            System.out.println("Target not found");
        } else {
            System.out.println("Target " + target + " found at index " + result);
        }
    }
}

if (low > high) { return -1; }

stop recursion if search range is invalid (target not found)

int mid = low + (high - low) / 2;

calculate middle index to split search range

if (arr[mid] == target) { return mid; }

check if middle element is target

else if (arr[mid] < target) { return binarySearch(arr, target, mid + 1, high); }

search right half if target is greater than middle element

else { return binarySearch(arr, target, low, mid - 1); }

search left half if target is less than middle element

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each recursive call halves the search range

Space: O(log n) due to recursive call stack depth proportional to log n

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by reducing search space quickly

Edge Cases

empty array

returns -1 immediately as low > high

DSA Java

if (low > high) { return -1; }

target not in array

recursion ends when low > high, returns -1

DSA Java

if (low > high) { return -1; }

single element array with target present

returns index 0 immediately if arr[0] == target

DSA Java

if (arr[mid] == target) { return mid; }

When to Use This Pattern

When you need to find an item quickly in a sorted list, use recursive binary search because it halves the search space each step.

Common Mistakes

Mistake: Calculating mid as (low + high) / 2 without handling integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly in recursive calls
Fix: Use mid + 1 for low when searching right half and mid - 1 for high when searching left half

Summary

It finds a target value in a sorted array by repeatedly dividing the search range in half using recursion.

Use it when you have a sorted list and want to find an element efficiently.

The key insight is checking the middle element and deciding which half to search next, cutting the search space quickly.

Practice

1. What is the main idea behind the binary search recursive approach when searching for a value in a sorted array?

easy

A. Check every element one by one from start to end

B. Sort the array first and then search linearly

C. Divide the array into halves and search recursively in the half where the value may exist

D. Use a stack to store all elements and pop until the value is found

Solution

1. Step 1: Understand binary search logic

   Binary search works by dividing the sorted array into two halves and deciding which half to search next based on comparison.

2. Step 2: Apply recursion in binary search

   The recursive approach calls the same function on the half where the target value could be, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the half where the value may exist -> Option C

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Binary search splits array, search half recursively [OK]

Common Mistakes:

• Thinking binary search checks every element
• Not using recursion or iteration to reduce search space
• Assuming array is unsorted

2. Which of the following is the correct base case condition in a recursive binary search function in Java?

easy

A. if (start < end) return -1;

B. if (start == end) return start;

C. if (array[mid] == target) return mid;

D. if (start > end) return -1;

Solution

1. Step 1: Identify base case for recursion end

   The base case ends recursion when the search space is invalid, i.e., start index is greater than end index.

2. Step 2: Confirm correct base case syntax

   Using if (start > end) return -1; correctly signals the target is not found.

3. Final Answer:

   if (start > end) return -1; -> Option D

4. Quick Check:

   Base case = start > end [OK]

Hint: Base case ends when start passes end [OK]

Common Mistakes:

• Using start == end as base case incorrectly
• Returning wrong index when target not found
• Confusing base case with target found condition

3. What will be the output of the following Java code snippet?

public class Test {
  public static int binarySearch(int[] arr, int start, int end, int target) {
    if (start > end) return -1;
    int mid = start + (end - start) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) return binarySearch(arr, start, mid - 1, target);
    else return binarySearch(arr, mid + 1, end, target);
  }
  public static void main(String[] args) {
    int[] data = {2, 4, 6, 8, 10};
    System.out.println(binarySearch(data, 0, data.length - 1, 6));
  }
}

medium

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Trace initial call and mid calculation

   Array is [2,4,6,8,10], start=0, end=4, target=6. Mid = 0 + (4-0)/2 = 2.

2. Step 2: Check if arr[mid] equals target

   arr[2] = 6 equals target 6, so return mid = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Calculate mid, compare, return index if match [OK]

Common Mistakes:

• Miscomputing mid index
• Returning wrong index when target found
• Confusing array indices

4. Identify the error in the following recursive binary search code snippet:

public static int binarySearch(int[] arr, int start, int end, int target) {
  if (start >= end) return -1;
  int mid = (start + end) / 2;
  if (arr[mid] == target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, start, mid - 1, target);
  else return binarySearch(arr, mid + 1, end, target);
}

medium

A. Base case condition should be start > end, not start >= end

B. Mid calculation should be start - end instead of start + end

C. Should return mid + 1 when target is greater

D. No error, code is correct

Solution

1. Step 1: Analyze base case condition

   Base case currently is if (start >= end) return -1;. This causes missing the case when start == end and target is at that index.

2. Step 2: Correct base case to allow checking when start == end

   Changing to if (start > end) return -1; ensures the single element at start==end is checked.

3. Final Answer:

   Base case condition should be start > end, not start >= end -> Option A

4. Quick Check:

   Base case must allow start == end check [OK]

Hint: Base case excludes start == end incorrectly [OK]

Common Mistakes:

• Using >= instead of > in base case
• Ignoring single element check
• Incorrect mid calculation

5. Given a sorted array with possible duplicate values, how can you modify the recursive binary search to find the first occurrence of a target value?

hard

A. Return mid immediately when arr[mid] == target

B. When arr[mid] == target, continue searching left half to find earlier occurrence

C. Search only the right half when arr[mid] == target

D. Use linear search after binary search to find first occurrence

Solution

1. Step 1: Understand duplicates and first occurrence

   Duplicates mean target can appear multiple times. To find first occurrence, we must check if earlier indices also have target.

2. Step 2: Modify recursive call when target found

   When arr[mid] == target, recursively search left half to find if target appears earlier. If none found, return current mid.

3. Final Answer:

   When arr[mid] == target, continue searching left half to find earlier occurrence -> Option B

4. Quick Check:

   Search left half on match for first occurrence [OK]

Hint: On match, search left half to find first occurrence [OK]

Common Mistakes:

• Returning first found index without checking left side
• Searching right half on match
• Using linear search unnecessarily