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 recursively

↓

If range invalid

↓

Return -1

Start with the whole array, find the middle element, compare with target, then recursively search 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 target in sorted array by dividing search range in half each call.

Execution Table

Step	Operation	Left	Right	Mid	arr[Mid]	Comparison	Action	Visual State
1	Start search	0	6	3	7	7 vs 3	7 > 3, search left half	[1, 3, 5, 7, 9, 11, 13]
2	Recursive call	0	2	1	3	3 vs 3	Found target, return 1	[1, 3, 5, 7, 9, 11, 13]
3	Return index	-	-	-	-	-	Return 1 as result	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 1, recursion ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
left	0	0	0	0
right	6	6	2	2
mid	-	3	1	1
arr[mid]	-	7	3	3
return value	-	-	1	1

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 target is not found. See Step 1 where left=0 and right=6, valid range, but if left > right, recursion stops.

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

To avoid integer overflow when left and right are large. This calculation safely finds the middle index. This is shown in Step 1 and Step 2 mid calculations.

Why does the recursion search left half when arr[mid] > target?

Because the array is sorted, so if middle element is bigger than target, target can only be in left half. This is shown in Step 1 where 7 > 3, so search left half.

Visual Quiz - 3 Questions

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

A 1

B 3

C 0

D 2

💡 Hint

Check the 'Mid' column in Step 2 of the execution_table.

At which step does the function find the target?

A Step 1

B Step 3

C Step 2

D None

💡 Hint

Look at the 'Action' column where it says 'Found target'.

If the target was 10, which half would the first recursive call search?

A Left half

B Right half

C Whole array

D No recursive call

💡 Hint

Refer to Step 1 where arr[mid] is compared to target to decide search half.

Concept Snapshot

Binary Search Recursive Approach:
- Start with left and right indices of array
- 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
- Stop when left > right (target not found)

Full Transcript

Binary Search Recursive Approach starts by checking if the search range is valid (left <= right). It calculates the middle index safely to avoid overflow. Then it compares the middle element with the target. If equal, it returns the index. If the middle element is greater than the target, it recursively searches the left half. Otherwise, it searches the right half. This process repeats until the target is found or the search range becomes invalid, indicating the target is not in the array.

Practice

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

easy

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

B. Divide the array into halves and search recursively in the half where the element can be

C. Sort the array first and then search linearly

D. Use a queue to store elements and search iteratively

Solution

1. Step 1: Understand binary search principle

   Binary search works by dividing the sorted array into two halves and deciding which half to search next based on comparison with the middle element.

2. Step 2: Apply recursion in binary search

   The recursive approach calls the same function on the half where the target element might be, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the half where the element can be -> Option B

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Remember: binary search splits array, searches half recursively [OK]

Common Mistakes:

• Thinking binary search checks every element
• Not using recursion to reduce search space
• Searching unsorted arrays with binary search

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

easy

A. if (low == high) return -1;

B. if (low < high) return -1;

C. if (low > high) return -1;

D. if (low >= high) return -1;

Solution

1. Step 1: Understand base case in recursion

   The base case stops recursion when the search space is invalid, meaning low index is greater than high index.

2. Step 2: Identify correct condition

   When low > high, it means the element is not found, so return -1 to indicate failure.

3. Final Answer:

   if (low > high) return -1; -> Option C

4. Quick Check:

   Base case = low > high [OK]

Hint: Base case ends when low index passes high index [OK]

Common Mistakes:

• Using low == high as base case incorrectly
• Returning wrong value in base case
• Not handling base case leading to infinite recursion

3. What will be the output of the following C code snippet using recursive binary search?

int binarySearch(int arr[], int low, int high, int x) {
  if (low > high) return -1;
  int mid = low + (high - low) / 2;
  if (arr[mid] == x) return mid;
  else if (arr[mid] > x) return binarySearch(arr, low, mid - 1, x);
  else return binarySearch(arr, mid + 1, high, x);
}

int main() {
  int arr[] = {2, 4, 6, 8, 10};
  int n = 5;
  int result = binarySearch(arr, 0, n - 1, 6);
  printf("%d", result);
  return 0;
}

medium

A. 2

B. 1

C. -1

D. 3

Solution

1. Step 1: Trace the recursive calls

   Initial call: low=0, high=4, mid=2, arr[2]=6 equals target 6, so return 2 immediately.

2. Step 2: Understand output

   The function returns index 2 where element 6 is found, so printf prints 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Element 6 found at index 2 [OK]

Hint: Check mid index and compare to target first [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Not returning correct index on match

4. Identify the error in the following recursive binary search function and select the fix:

int binarySearch(int arr[], int low, int high, int x) {
  if (low >= high) return -1;
  int mid = (low + high) / 2;
  if (arr[mid] == x) return mid;
  else if (arr[mid] > x) return binarySearch(arr, low, mid - 1, x);
  else return binarySearch(arr, mid + 1, high, x);
}

medium

A. Return mid + 1 instead of mid when found

B. Change mid calculation to mid = low - (high - low) / 2;

C. Remove else if condition and use only if

D. Change base case to if (low > high) return -1;

Solution

1. Step 1: Analyze base case condition

   The base case uses if (low >= high) which incorrectly stops search when low equals high, missing the last element.

2. Step 2: Correct base case

   It should be if (low > high) to allow checking when low equals high, ensuring all elements are searched.

3. Final Answer:

   Change base case to if (low > high) return -1; -> Option D

4. Quick Check:

   Base case must allow low == high [OK]

Hint: Base case must be low > high, not low >= high [OK]

Common Mistakes:

• Stopping recursion too early
• Incorrect mid calculation causing infinite recursion
• Returning wrong index on match

5. Given a sorted array arr = {1, 3, 5, 7, 9, 11, 13}, you want to find the index of element 8 using recursive binary search. What will be the sequence of mid indices checked before concluding the element is not found?

hard

A. [3, 5, 4]

B. [3, 1, 0]

C. [3, 1, 2]

D. [3, 4, 5]

Solution

1. Step 1: Calculate first mid index

   Initial low=0, high=6, mid = (0+6)/2 = 3, arr[3]=7 less than 8, search right half next.

2. Step 2: Calculate second mid index

   New low=4, high=6, mid = (4+6)/2 = 5, arr[5]=11 greater than 8, search left half next.

3. Step 3: Calculate third mid index

   New low=4, high=4, mid = (4+4)/2 = 4, arr[4]=9 greater than 8, search left half next low=4, high=3 ends recursion.

4. Final Answer:

   [3, 5, 4] -> Option A

5. Quick Check:

   Mid indices checked = 3, 5, 4 [OK]

Hint: Track low, high, mid updates carefully each recursion [OK]

Common Mistakes:

• Not updating low and high correctly
• Miscomputing mid index
• Stopping search too early