Binary Search Recursive Approach in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the binary search algorithm?

Binary search works by repeatedly dividing a sorted list in half to find a target value quickly. It compares the target with the middle element and decides which half to search next.

beginner

In the recursive binary search, what are the base cases?

The base cases are when the search range is invalid (start index > end index), meaning the target is not found, or when the middle element equals the target, meaning the search is successful.

beginner

Why must the array be sorted for binary search to work?

Because binary search decides which half to search based on comparisons, the array must be sorted to ensure that all smaller elements are on one side and larger on the other.

intermediate

What is the time complexity of binary search and why?

The time complexity is O(log n) because each step halves the search space, quickly reducing the number of elements to check.

intermediate

Show the recursive call structure of binary search when searching for 7 in [1, 3, 5, 7, 9].

First call checks middle element 5 (index 2), 7 > 5 so search right half [7, 9]. Second call checks middle element 7 (index 3), found target, recursion ends.

What should happen if the start index becomes greater than the end index in recursive binary search?

A Return -1 or not found

B Continue searching

C Restart the search

D Return the middle element

When start index > end index, it means the target is not in the array, so the function returns -1 or a not found signal.

Which condition indicates that the target is found in recursive binary search?

A middle element == target

B start index > end index

C target < middle element

D target > middle element

If the middle element equals the target, the search is successful and the index is returned.

What is the first step in each recursive call of binary search?

A Print the array

B Sort the array

C Swap elements

D Calculate the middle index

Each recursive call calculates the middle index to decide where to search next.

Why is recursion useful in binary search?

A It increases the search space

B It automatically handles dividing the search space

C It prints the array

D It sorts the array

Recursion helps by calling the function on smaller parts of the array, naturally dividing the search space.

What must be true about the input array for binary search to work correctly?

A It must have duplicates

B It must be empty

C It must be sorted

D It must be reversed

Binary search requires a sorted array to correctly decide which half to search.

Explain how recursive binary search works step-by-step.

Think about how the problem size reduces each time.

Describe why binary search is faster than linear search on sorted arrays.

Focus on how quickly the search space shrinks.

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