Binary Search Recursive Approach in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the middle index in the binary search.

DSA C++

int mid = low + ([1] - low) / 2;

Drag options to blanks, or click blank then click option'

Amid

Bhigh

Clow

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using low twice instead of high and low.

Using size instead of high.

The middle index is calculated using the high and low indices to avoid overflow.

2fill in blank

medium

Complete the code to return the index when the target is found.

DSA C++

if (arr[mid] == target) return [1];

Drag options to blanks, or click blank then click option'

Alow

B-1

Cmid

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Returning low or high instead of mid.

Returning -1 which means not found.

Return the middle index where the target is found.

3fill in blank

hard

Fix the error in the recursive call for searching the left half.

DSA C++

return binarySearch(arr, low, [1] - 1, target);

Drag options to blanks, or click blank then click option'

Atarget

Blow

Chigh

Dmid

Attempts:

3 left

💡 Hint

Common Mistakes

Using low or high instead of mid.

Passing target as index.

To search the left half, we reduce the high index to mid - 1.

4fill in blank

hard

Fill both blanks to complete the recursive call for searching the right half.

DSA C++

return binarySearch(arr, [1] + 1, [2], target);

Drag options to blanks, or click blank then click option'

Amid

Blow

Chigh

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping low and high.

Using target as index.

To search the right half, start from mid + 1 to high index.

5fill in blank

hard

Fill all three blanks to complete the base case and recursive calls of binary search.

DSA C++

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

Drag options to blanks, or click blank then click option'

A-1

Bmid

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Returning wrong values in base case or recursive calls.

Using low instead of mid in recursive calls.

Return -1 if not found, return mid if found, and use mid - 1 to search left half.

Practice

1. What is the main idea behind the binary search recursive approach?

easy

A. Use recursion to reverse the array before searching

B. Divide the array into halves and search recursively in the relevant half

C. Sort the array recursively before searching

D. Search every element one by one recursively

Solution

1. Step 1: Understand binary search logic

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

2. Step 2: Apply recursion in binary search

   Recursion calls the same function on the half where the target might be, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the relevant half -> Option B

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Think divide and conquer, search half each time [OK]

Common Mistakes:

• Searching all elements recursively instead of half
• Sorting inside the search function
• Not reducing search space correctly

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

easy

A. if (start > end) return -1;

B. if (start == end) return start;

C. if (start < end) return -1;

D. if (start == 0) return 0;

Solution

1. Step 1: Identify when search should stop

   The search should stop when the start index is greater than the end index, meaning the element is not found.

2. Step 2: Confirm base case condition

   Checking if start > end returns -1 to indicate the target is missing.

3. Final Answer:

   if (start > end) return -1; -> Option A

4. Quick Check:

   Base case = start > end means not found [OK]

Hint: Stop when start passes end, return -1 [OK]

Common Mistakes:

• Using start == end as base case incorrectly
• Returning wrong index when not found
• Confusing start and end conditions

3. What will be the output of the following C++ code?

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

int main() {
  int arr[] = {2, 4, 6, 8, 10};
  int index = binarySearch(arr, 0, 4, 6);
  std::cout << index;
  return 0;
}

medium

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Identify the target and array

   The array is {2,4,6,8,10} and target is 6.

2. Step 2: Trace recursive calls

   First mid = 2 (index 2), arr[2] = 6 matches target, so return 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check middle element first, return index if match [OK]

Common Mistakes:

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

4. Find the error in this recursive binary search function:

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

medium

A. Mid calculation should be start - end instead of start + end

B. Return value should be target, not index

C. Base case condition should be start > end, not start >= end

D. Recursive calls should swap start and end

Solution

1. Step 1: Analyze base case condition

   The base case incorrectly uses start >= end, which misses checking when start == end.

2. Step 2: Correct base case for full search

   It should be start > end to allow checking the last element at start == end.

3. Final Answer:

   Base case condition should be start > end, not start >= end -> Option C

4. Quick Check:

   Base case = start > end to stop [OK]

Hint: Base case must allow start == end check [OK]

Common Mistakes:

• Using >= instead of > in base case
• Wrong mid calculation formula
• Returning wrong values

5. Given a sorted array with possible duplicate elements, how can you modify the recursive binary search to find the first occurrence of a target value?

hard

A. Use linear search after binary search to find first occurrence

B. Return mid immediately when arr[mid] == target

C. Search right half only when arr[mid] == target

D. When arr[mid] == target, continue searching left half to find earlier occurrence

Solution

1. Step 1: Understand duplicates in sorted array

   Duplicates mean target can appear multiple times; we want the first index.

2. Step 2: Modify recursive search on match

   When arr[mid] == target, recursively search left half to check for earlier occurrence, else return mid.

3. Step 3: Implement logic

   If left recursive call returns valid index, return it; otherwise return mid.

4. Final Answer:

   When arr[mid] == target, continue searching left half to find earlier occurrence -> Option D

5. Quick Check:

   Find first occurrence = search left on match [OK]

Hint: On match, search left half to find first occurrence [OK]

Common Mistakes:

• Returning first found index without checking left side
• Searching right half on match
• Using linear search unnecessarily