Binary Search Recursive Approach in DSA Javascript - Execution Trace

Concept Flow - Binary Search Recursive Approach

Start with full array

↓

Calculate middle index

↓

Compare middle element with target

↓

Equal?

↓

Return mid

↓

Search right half

↓

Repeat steps

↓

Not found? Return -1

Start with the full array, find the middle element, compare with target, then recursively search left or right half until found or empty.

Execution Sample

DSA Javascript

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

This recursive function searches for target in sorted array arr between left and right indices.

Execution Table

Step	Operation	Left	Right	Mid	Mid Value	Comparison	Next Action	Visual State
1	Start search	0	6	3	7	target=5 < 7	Search left half	[1, 3, 5, 7, 9, 11, 13]
2	Recursive call	0	2	1	3	target=5 > 3	Search right half	[1, 3, 5]
3	Recursive call	2	2	2	5	target=5 == 5	Return index 2	[5]
4	Return result	-	-	-	-	-	Found target at index 2	[5]

💡 Search ends when target is found at index 2 or when left > right (not in this case).

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
left	0	0	0	2	2
right	6	6	2	2	2
mid	-	3	1	2	2
midValue	-	7	3	5	5
target	5	5	5	5	5

Key Moments - 3 Insights

Why do we check if left > right before calculating mid?

Because when left > right, the search space is empty, so the target is not found.

Why do we calculate mid as Math.floor((left + right) / 2)?

To find the middle index between left and right, ensuring we split the array roughly in half each time, as seen in steps 1 to 3 in the execution_table.

Why do we recurse on left half with right = mid - 1 and on right half with left = mid + 1?

Because mid has been checked already, so we exclude it to avoid infinite loops. This is clear in steps 1 and 2 where the search space shrinks.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of mid at Step 2?

A 3

B 2

C 1

D 0

💡 Hint

Check the 'Mid' column in execution_table row 2.

At which step does the condition left > right become true and cause the search to stop?

A Never in this example

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Operation' and 'Next Action' columns in execution_table; the search ends by finding the target, not by left > right.

If the target was 10 instead of 5, what would be the next action at Step 2?

A Search left half

B Search right half

C Return index 2

D Return -1

💡 Hint

Compare target with midValue at Step 2 in execution_table to decide direction.

Concept Snapshot

Binary Search Recursive Approach:
- Input: sorted array, target, left and right indices
- Calculate mid = floor((left + right)/2)
- If arr[mid] == target, return mid
- If target < arr[mid], search left half (left to mid-1)
- Else search right half (mid+1 to right)
- Stop when left > right (target not found)

Full Transcript

Binary Search Recursive Approach starts by checking if the search space is empty (left > right). If not, it calculates the middle index and compares the middle element with the target. If equal, it returns the index. If the target is smaller, it recursively searches the left half. If larger, it searches the right half. This process repeats until the target is found or the search space is empty. The execution table shows each recursive call's left, right, mid, and decision. Variables like left, right, mid, and midValue change as the recursion narrows the search. Key moments clarify why the base case is checked first, how mid is calculated, and why the search space excludes mid in recursive calls. The visual quiz tests understanding of mid calculation, termination condition, and direction choice based on target comparison.

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