Binary Search Recursive Approach in DSA C++ - Execution Trace

Concept Flow - Binary Search Recursive Approach

Start with full array range

↓

Calculate middle index

↓

Compare middle element with target

↓

Return mid

↓

Repeat until found or range invalid

↓

Return -1 if not found

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

Execution Sample

DSA C++

int binarySearch(int arr[], int left, int right, int target) {
  if (left > right) return -1;
  int mid = left + (right - left) / 2;
  if (arr[mid] == target) return mid;
  if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
  return binarySearch(arr, mid + 1, right, target);
}

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

Execution Table

Step	Operation	Left	Right	Mid	arr[Mid]	Comparison	Next Range	Result
1	Start search	0	6	3	7	7 vs 3: 7 > 3	Left half (0 to 2)
2	Recursive call	0	2	1	3	3 vs 3: 3 == 3	Found target	Return 1
3	Return							1

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
left	0	0	0	0
right	6	2	2	2
mid	N/A	3	1	1
arr[mid]	N/A	7	3	3
result	N/A	N/A	1	1

Key Moments - 3 Insights

Why do we calculate mid as left + (right - left) / 2 instead of (left + right) / 2?

Calculating mid as left + (right - left) / 2 prevents integer overflow when left and right are large, as shown in Step 1 of the execution_table.

What happens when left becomes greater than right?

When left > right, it means the target is not in the array, so the function returns -1 and stops recursion, as explained in the exit_note.

Why do we return mid immediately when arr[mid] == target?

Because we found the target at index mid, so no further search is needed. This is shown in Step 2 where the comparison is equal and the function returns mid.

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Mid' column in the first row of the execution_table.

At which step does the function find the target value?

A Step 1

B Step 2

C Step 3

D It never finds the target

💡 Hint

Look at the 'Comparison' and 'Result' columns in the execution_table.

If the target was 10 instead of 3, what would happen at Step 1?

A Search right half (4 to 6)

B Search left half (0 to 2)

C Return mid immediately

D Return -1 immediately

💡 Hint

Compare arr[mid] with target in Step 1 and decide which half to search next.

Concept Snapshot

Binary Search Recursive Approach:
- Input: sorted array, left index, right index, target
- Calculate mid = left + (right - left) / 2
- If arr[mid] == target, return mid
- If arr[mid] > target, search left half recursively
- Else, search right half recursively
- Return -1 if target not found (left > right)

Full Transcript

Binary Search Recursive Approach starts by checking the middle element of the current search range. If the middle element equals the target, it returns the index immediately. If the middle element is greater than the target, it recursively searches the left half. If less, it searches the right half. This process repeats until the target is found or the search range is invalid (left > right), returning -1. The mid index is calculated carefully to avoid overflow. The execution table shows the step-by-step recursive calls and comparisons.