Binary Search Recursive Approach in DSA Typescript

Mental Model

Binary search splits a sorted list in half to find a target quickly by checking the middle element and searching only the half that could contain the target.

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

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indexes:     [0, 1, 2, 3, 4,  5,  6]
Pointers:    low -> 0, high -> 6, mid -> 3 (value 7)

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, check value 7

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

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

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

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

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

Step 3: Calculate mid index between low=4 and high=6, mid=5, check value 11

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

Why: Check middle of new subarray to narrow search

Step 4: Since 9 < 11, 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 it is less than mid value

Step 5: Calculate mid index between low=4 and high=4, mid=4, check value 9

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

Why: Check the only element left

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

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

Why: Mid value equals target, search ends

Result:

[1, 3, 5, 7, [9], 11, 13] target index = 4

Annotated Code

DSA Typescript

class BinarySearch {
  static recursiveSearch(arr: number[], target: number, low: number, high: number): number {
    if (low > high) {
      return -1; // target not found
    }
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      return mid; // target found
    } else if (arr[mid] < target) {
      return this.recursiveSearch(arr, target, mid + 1, high); // search right half
    } else {
      return this.recursiveSearch(arr, target, low, mid - 1); // search left half
    }
  }
}

// Driver code
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 9;
const index = BinarySearch.recursiveSearch(arr, target, 0, arr.length - 1);
if (index !== -1) {
  console.log(`Target found at index ${index}`);
} else {
  console.log("Target not found");
}

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

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

const mid = Math.floor((low + high) / 2);

calculate middle index of current search range

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

check if middle element is the target

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

search right half if target is greater than mid value

else { return this.recursiveSearch(arr, target, low, mid - 1); }

search left half if target is less than mid value

Output

Target 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 since low > high

DSA Typescript

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

target not in array

recursion ends when low > high and returns -1

DSA Typescript

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

single element array with target present

returns index 0 immediately if arr[0] equals target

DSA Typescript

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 divides the search space in half each time.

Common Mistakes

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

Mistake: Calculating mid as (low + high) / 2 without floor causing float index
Fix: Use Math.floor to get integer mid index

Summary

It finds a target value in a sorted array by recursively checking the middle element and searching half the array.

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

The key insight is cutting the search space in half each step to quickly zero in on the target.