Binary Search Recursive Approach in DSA Typescript - Execution Trace

Concept Flow - Binary Search Recursive Approach

Start with full array and target

↓

Calculate middle index

↓

Compare middle element with target

↓

Search left half

↓

Return result

The recursive binary search splits the array, compares the middle element with the target, then searches left or right half recursively until found or empty.

Execution Sample

DSA Typescript

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);
}

This code recursively searches for target in a sorted array by dividing the search range in half each time.

Execution Table

Step	Operation	Left	Right	Mid	Compare arr[mid] with target	Next Call Range	Result
1	Start search	0	6	3	arr[3]=7 vs target=5: 7 > 5	Search left half (0 to 2)
2	Recursive call	0	2	1	arr[1]=3 vs target=5: 3 < 5	Search right half (2 to 2)
3	Recursive call	2	2	2	arr[2]=5 vs target=5: equal	Found target at index 2	2
4	Return result						2

💡 Target found at index 2, recursion ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
left	0	0	2	2	2
right	6	2	2	2	2
mid		3	1	2	2
result				2	2

Key Moments - 3 Insights

Why do we check if left > right at the start?

Because when left passes right, it means the search range is empty and the target is not found. This is shown in step 1 where if left > right, we return -1 to stop recursion.

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

We pick the middle index to split the array into two halves. Using floor ensures mid is an integer index. This is shown in steps 1-3 where mid changes as the search range changes.

How does recursion narrow down the search range?

Each recursive call updates left or right to mid-1 or mid+1 depending on comparison, reducing the search space. See steps 1 and 2 where next call ranges shrink towards the target.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of mid at step 2?

A 2

B 3

C 1

D 0

💡 Hint

Check the 'Mid' column in row for step 2 in the execution_table.

At which step does the function find the target?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Compare arr[mid] with target' and 'Result' columns to see when target is found.

If the target was 8 instead of 5, what would be the next call range after step 1?

A Search right half (4 to 6)

B Search right half (3 to 6)

C Search left half (0 to 2)

D Search left half (0 to 3)

💡 Hint

Compare arr[mid]=7 with target=8 at step 1 and see which half is searched next.

Concept Snapshot

Binary Search Recursive Approach:
- Input: sorted array, target, left index, right index
- Calculate mid = floor((left + right)/2)
- If arr[mid] == target, return mid
- If arr[mid] > target, 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 splits a sorted array by comparing the middle element to the target. If equal, it returns the index. If the middle element is greater, it searches the left half recursively. If smaller, it searches the right half recursively. The recursion stops when the search range is empty (left > right). This method efficiently finds the target or returns -1 if not found.