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.

Practice

1. What is the main idea behind the binary search recursive approach?

easy

A. Search each element one by one from start to end

B. Divide the array into halves and search recursively in the correct half

C. Sort the array after each recursive call

D. Use a queue to store elements for searching

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 the middle element.

2. Step 2: Apply recursion in binary search

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

3. Final Answer:

   Divide the array into halves and search recursively in the correct half -> Option B

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Remember: binary search splits array, then recurses [OK]

Common Mistakes:

• Thinking binary search checks every element
• Sorting array inside recursion
• Using linear search logic

2. Which of the following is the correct TypeScript function signature for a recursive binary search?

easy

A. function binarySearch(arr: number[], target: string): boolean

B. function binarySearch(arr: string[], target: number): number

C. function binarySearch(arr: number[], target: number, left: number, right: number): number

D. function binarySearch(arr: number[], target: number): void

Solution

1. Step 1: Check parameters needed for recursion

   Recursive binary search needs the array, target, and the current left and right indices to search between.

2. Step 2: Verify return type

   The function returns the index of the target if found, so the return type is number.

3. Final Answer:

   function binarySearch(arr: number[], target: number, left: number, right: number): number -> Option C

4. Quick Check:

   Parameters + return type match recursive binary search [OK]

Hint: Recursive binary search needs left and right indices [OK]

Common Mistakes:

• Missing left and right parameters
• Wrong return type (void or boolean)
• Mismatched array and target types

3. What will be the output of the following TypeScript code?

function binarySearch(arr: number[], target: number, left: number, right: number): number {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

const nums = [2, 4, 6, 8, 10];
console.log(binarySearch(nums, 6, 0, nums.length - 1));

medium

A. 2

B. 1

C. -1

D. 3

Solution

1. Step 1: Identify middle index and compare

   Initial call: left=0, right=4, mid=2. arr[2] = 6 matches target 6.

2. Step 2: Return index when found

   Since arr[mid] equals target, function returns mid = 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check middle element first, then recurse [OK]

Common Mistakes:

• Miscomputing mid index
• Returning wrong index
• Confusing array values with indices

4. Find the error in this recursive binary search function:

function binarySearch(arr: number[], target: number, left: number, right: number): number {
  if (left >= right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

medium

A. The base case condition should be left > right, not left >= right

B. The mid calculation is incorrect

C. The function should return boolean instead of number

D. The recursive calls have wrong parameters

Solution

1. Step 1: Analyze base case condition

   The base case currently returns -1 if left >= right, but it should allow left == right to check that element.

2. Step 2: Correct base case to left > right

   Changing to left > right ensures the search includes the last element before stopping.

3. Final Answer:

   The base case condition should be left > right, not left >= right -> Option A

4. Quick Check:

   Base case must allow left == right [OK]

Hint: Base case stops when left passes right, not equals [OK]

Common Mistakes:

• Stopping search too early with wrong base case
• Miscomputing mid index
• Wrong return type

5. Given a sorted array arr = [1, 3, 5, 7, 9, 11, 13], write a recursive binary search call to find the index of 7. What will be the sequence of mid indices checked?

hard

A. [3, 5]

B. [3, 1]

C. [3, 1, 2]

D. [3]

Solution

1. Step 1: Calculate initial mid index

   left=0, right=6, mid = floor((0+6)/2) = 3. arr[3] = 7 matches target immediately.

2. Step 2: No further recursive calls needed

   Since target found at first mid, no other mid indices are checked.

3. Final Answer:

   [3] -> Option D

4. Quick Check:

   Target found at first mid index 3 [OK]

Hint: First mid often finds target if array is balanced [OK]

Common Mistakes:

• Assuming multiple recursive calls always happen
• Miscomputing mid index
• Confusing indices with values