Binary Search Recursive Approach in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search on Sorted Array

What is the output of the following C++ code that performs a recursive binary search for the value 7 in the array?

DSA C++

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

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, 7);
    std::cout << result << std::endl;
    return 0;
}

A 3

B 2

C -1

D 4

💡 Hint

Remember that array indexing starts at 0 and binary search returns the index of the found element.

The value 7 is at index 3 in the array {1, 3, 5, 7, 9, 11}. The recursive binary search returns this index.

❓ Predict Output

intermediate

Result of Recursive Binary Search When Element Not Present

What will be the output of this recursive binary search code when searching for 8 in the array?

DSA C++

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

int main() {
    int arr[] = {2, 4, 6, 10, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, 8);
    std::cout << result << std::endl;
    return 0;
}

A 0

B 2

C 3

D -1

💡 Hint

If the element is not found, the function returns -1.

Since 8 is not in the array, the recursive calls eventually return -1 indicating not found.

🧠 Conceptual

advanced

Understanding Recursive Binary Search Base Case

In the recursive binary search function, what is the purpose of the base case condition 'if (right < left)'?

A It means the search space is empty and the element is not present.

B It indicates the element has been found at index right.

C It resets the search to the full array again.

D It swaps the left and right indices to continue searching.

💡 Hint

Think about what happens when the search boundaries cross.

When right < left, it means there are no elements left to search, so the element is not found.

❓ Predict Output

advanced

Output of Recursive Binary Search with Duplicate Elements

Given the array with duplicates, what index will the recursive binary search return when searching for 5?

DSA C++

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

int main() {
    int arr[] = {1, 3, 5, 5, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, 5);
    std::cout << result << std::endl;
    return 0;
}

A 4

B 3

C 2

D -1

💡 Hint

Binary search returns the first found index, not necessarily the first occurrence.

The mid calculation first finds index 3 where 5 is located, so it returns 3.

🧠 Conceptual

expert

Time Complexity of Recursive Binary Search

What is the time complexity of the recursive binary search algorithm on a sorted array of size n?

A O(n log n)

B O(n)

C O(log n)

D O(1)

💡 Hint

Each recursive call halves the search space.

Binary search divides the array in half each time, leading to logarithmic time complexity O(log n).