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.