Binary Search Recursive Approach in DSA Javascript

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 your word is before or after that page, and repeating the process on the chosen half.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
          ↑           ↑
        start       end
          ↑
        mid

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 start=0 and end=6, mid=3; check value at mid=7

[1, 3, 5, [7], 9, 11, 13] start=0 end=6 mid=3

Why: We check the middle to decide which half to search next

Step 2: Since 9 > 7, search right half: start=4, end=6

[1, 3, 5, 7, [9], 11, 13] start=4 end=6

Why: Target is greater than mid value, so it must be in the right half

Step 3: Calculate mid index between start=4 and end=6, mid=5; check value at mid=11

[1, 3, 5, 7, 9, [11], 13] start=4 end=6 mid=5

Why: Check middle of the new subarray to narrow down search

Step 4: Since 9 < 11, search left half: start=4, end=4

[1, 3, 5, 7, [9], 11, 13] start=4 end=4

Why: Target is less than mid value, so it must be in the left half

Step 5: Calculate mid index between start=4 and end=4, mid=4; check value at mid=9

[1, 3, 5, 7, [9], 11, 13] start=4 end=4 mid=4

Why: Only one element left, check if it is the target

Step 6: Found target 9 at index 4, return index

[1, 3, 5, 7, [9], 11, 13]

Why: Target found, end search

Result:

Final state: [1, 3, 5, 7, [9], 11, 13]
Answer: index 4

Annotated Code

DSA Javascript

class BinarySearch {
  static recursiveSearch(arr, target, start = 0, end = arr.length - 1) {
    if (start > end) return -1; // base case: target not found

    const mid = Math.floor((start + end) / 2); // find middle index

    if (arr[mid] === target) {
      return mid; // target found
    } else if (target < arr[mid]) {
      return this.recursiveSearch(arr, target, start, mid - 1); // search left half
    } else {
      return this.recursiveSearch(arr, target, mid + 1, end); // search right half
    }
  }
}

// Driver code
const array = [1, 3, 5, 7, 9, 11, 13];
const target = 9;
const index = BinarySearch.recursiveSearch(array, target);
console.log(index !== -1 ? `Found target ${target} at index ${index}` : 'Target not found');

if (start > end) return -1; // base case: target not found

stop recursion when search space is empty

const mid = Math.floor((start + end) / 2); // find middle index

calculate middle index to split array

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

check if middle element is target

else if (target < arr[mid]) { return this.recursiveSearch(arr, target, start, mid - 1); }

search left half if target is smaller

else { return this.recursiveSearch(arr, target, mid + 1, end); }

search right half if target is larger

Output

Found target 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space

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 exponentially

Edge Cases

empty array

returns -1 immediately as start > end

DSA Javascript

if (start > end) return -1; // base case: target not found

target not in array

recursion ends when start > end, returns -1

DSA Javascript

if (start > end) return -1; // base case: target not found

array with one element

checks single element, returns index if match or -1 if not

DSA Javascript

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

When to Use This Pattern

When you need to find an item quickly in a sorted list, reach for recursive binary search because it cuts the search space in half each step.

Common Mistakes

Mistake: Not updating start or end correctly in recursive calls causing infinite recursion
Fix: Ensure start and end are adjusted to mid - 1 or mid + 1 respectively to shrink search space

Mistake: Calculating mid as (start + end) without floor causing float index
Fix: Use Math.floor to get integer mid index

Mistake: Not handling base case when start > end leading to stack overflow
Fix: Add base case to return -1 when start > end

Summary

It finds a target value in a sorted array by repeatedly splitting 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 to decide which half to search next, cutting the problem size in half each time.