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.