Binary Search Recursive Approach in DSA C++ - Build from Scratch

Binary Search Recursive Approach

📖 Scenario: Imagine you have a sorted list of book IDs in a library. You want to quickly find if a certain book ID is available using a smart method called binary search.

🎯 Goal: You will build a recursive binary search function in C++ that checks if a given book ID exists in the sorted list.

📋 What You'll Learn

Create a sorted array of integers called bookIDs with the values {101, 203, 305, 407, 509}.

Create two integer variables called left and right to represent the start and end indexes of the array.

Write a recursive function called binarySearch that takes bookIDs, left, right, and a target key as parameters and returns the index of key if found, or -1 if not found.

Call the binarySearch function to search for the book ID 305.

Print the result index returned by binarySearch.

💡 Why This Matters

🌍 Real World

Binary search is used in many software systems to quickly find data in sorted lists, such as searching for a contact in a phone book or a product in an online store.

💼 Career

Understanding binary search and recursion is fundamental for software developers, especially when working with algorithms and data structures to optimize search operations.

1

Create the sorted array of book IDs

Create an integer array called bookIDs with these exact values: {101, 203, 305, 407, 509}.

DSA C++

# Create the sorted array bookIDs with the given values
# Your code here

Hint

Use C++ array syntax with the exact values inside curly braces.

2

Set the left and right index variables

Create two integer variables called left and right. Set left to 0 and right to 4 (the last index of bookIDs).

DSA C++

int bookIDs[] = {101, 203, 305, 407, 509};
# Create left and right variables with values 0 and 4
# Your code here

Hint

Remember array indexes start at 0, so the last index is 4 for 5 elements.

3

Write the recursive binarySearch function

Write a recursive function called binarySearch that takes parameters int arr[], int left, int right, and int key. It should return the index of key if found, or -1 if not found. Use the binary search logic with recursion.

DSA C++

int bookIDs[] = {101, 203, 305, 407, 509};
int left = 0;
int right = 4;

// Write the recursive binarySearch function below
# Your code here

Hint

Use the middle index to split the array and call the function recursively on the correct half.

4

Call binarySearch and print the result

Call the binarySearch function with bookIDs, left, right, and the key 305. Store the result in an integer variable called result. Then print result.

DSA C++

int bookIDs[] = {101, 203, 305, 407, 509};
int left = 0;
int right = 4;

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

// Call binarySearch for key 305 and print the result
# Your code here

Hint

Store the returned index in result and print it using std::cout.

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