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.

Practice

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

easy

A. Divide the array into halves and search recursively in the half where the value can be.

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

C. Sort the array first and then search linearly.

D. Use a loop to check elements 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: Recognize recursive approach

   In recursion, the function calls itself on the half where the target value may exist, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the half where the value can be. -> Option A

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Remember: binary search splits array, recursion repeats on half [OK]

Common Mistakes:

• Thinking binary search checks every element linearly
• Confusing recursion with iteration
• Not requiring the array to be sorted

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

easy

A. if (array.length == 0) return 0;

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

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

D. if (mid == target) return mid + 1;

Solution

1. Step 1: Identify base case meaning

   The base case stops recursion when the search space is empty, which happens if start index passes end index.

2. Step 2: Match base case condition

   The condition start > end means no elements left to search, so return -1 to indicate not found.

3. Final Answer:

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

4. Quick Check:

   Base case = empty search space [OK]

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

Common Mistakes:

• Using incorrect comparison like start == end as base case
• Returning wrong index or value in base case
• Confusing base case with recursive step

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

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

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

medium

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Trace initial call

   Start=0, end=4, mid=2 (element 6). Since arr[mid] == target (6), return mid = 2.

2. Step 2: Confirm output

   The function returns 2 immediately without further recursion.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check mid index value first to find target quickly [OK]

Common Mistakes:

• Miscomputing mid index
• Confusing index with value
• Forgetting zero-based indexing

4. Identify the error in the following recursive binary search function and choose the correct fix.

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

medium

A. Change mid calculation to (start + end + 1) / 2;

B. Remove else if and use only if statements.

C. Return mid + 1 when found instead of mid;

D. Change base case to if (start > end) return -1;

Solution

1. Step 1: Analyze base case condition

   The base case incorrectly uses start >= end, which misses the case when start == end and the element could still be at that index.

2. Step 2: Correct base case

   Changing it to start > end ensures the search includes the last element before stopping.

3. Final Answer:

   Change base case to if (start > end) return -1; -> Option D

4. Quick Check:

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

Hint: Base case should allow checking when start equals end [OK]

Common Mistakes:

• Stopping search too early by wrong base case
• Changing mid calculation unnecessarily
• Returning wrong index on success

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. Search right half only when arr[mid] == target.

B. Return mid immediately when arr[mid] == target without further search.

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

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

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any occurrence, but to find first occurrence, we must check if earlier duplicates exist.

2. Step 2: Modify recursion on match

   When arr[mid] == target, recursively search left half to find if an earlier occurrence exists; if none, mid is first occurrence.

3. Final Answer:

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

4. Quick Check:

   Find first occurrence by searching left on match [OK]

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

Common Mistakes:

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