Binary Search as Divide and Conquer in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search Mid Calculation

What is the output of the following C++ code snippet that performs binary search on a sorted array to find the index of the target 7?

DSA C++

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

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int index = binarySearch(arr, 0, 5, 7);
    std::cout << index;
    return 0;
}

A 3

B -1

C 2

D 4

💡 Hint

Remember that array indexing starts at 0 and the target 7 is in the middle of the array.

The target 7 is at index 3 in the array. The binary search calculates mid as 3 and finds the target immediately.

🧠 Conceptual

intermediate

Divide and Conquer Principle in Binary Search

Which statement best describes how binary search uses the divide and conquer approach?

A It sorts the array first and then performs a linear search.

B It searches both halves of the array simultaneously to find the target faster.

C It divides the array into multiple small parts and searches all parts in parallel.

D It divides the array into two halves and recursively searches only the half that may contain the target.

💡 Hint

Think about how binary search reduces the search space after each comparison.

Binary search divides the array into two halves and only continues searching in the half where the target could be, ignoring the other half.

❓ Predict Output

advanced

Output of Recursive Binary Search with Edge Case

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

DSA C++

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

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

A -1

B 2

C 3

D 4

💡 Hint

Check the middle element and how the recursion narrows down the search.

The target 8 is at index 3. The recursive calls find it correctly and return 3.

🔧 Debug

advanced

Identify the Error in Binary Search Implementation

What error will this binary search code produce when searching for 9 in the array?

DSA C++

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

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int idx = binarySearch(arr, 0, 4, 9);
    std::cout << idx;
    return 0;
}

A It causes a runtime error due to out-of-bounds access.

B It returns -1 even though 9 is in the array.

C It returns the wrong index 2 instead of 3.

D It causes an infinite loop.

💡 Hint

Check the loop condition and how it affects the search space.

The loop condition 'left < right' excludes the case when left == right, so the target at index 4 is missed and -1 is returned.

🚀 Application

expert

Number of Recursive Calls in Binary Search

Given a sorted array of size 31, what is the maximum number of recursive calls made by a binary search to find a target or conclude it is not present?

A 6

B 5

C 4

D 7

💡 Hint

Think about how many times you can divide 31 by 2 until you reach 1.

Binary search halves the search space each call. For 31 elements, maximum calls = ceil(log2(31) + 1) = 6.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It divides the search space into two halves and discards one half each time.

B. It searches every element one by one until it finds the target.

C. It sorts the array before searching for the element.

D. It uses recursion to add elements to the array.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the array into two halves and decides which half to continue searching based on the middle element.

2. Step 2: Identify the main action in binary search

   It discards the half where the target cannot be, reducing the search space quickly.

3. Final Answer:

   It divides the search space into two halves and discards one half each time. -> Option A

4. Quick Check:

   Divide and conquer = split and discard half [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Thinking binary search checks every element
• Confusing binary search with linear search
• Assuming binary search sorts the array

2. Which of the following is the correct syntax to calculate the middle index in binary search in C++?

easy

A. int mid = (low + high) / 2;

B. int mid = (low * high) / 2;

C. int mid = low + (high - low) / 2;

D. int mid = (low - high) / 2;

Solution

1. Step 1: Understand why to avoid overflow

   Using (low + high) / 2 can cause overflow if low and high are large integers.

2. Step 2: Use safe middle calculation

   Calculating mid as low + (high - low) / 2 avoids overflow by subtracting before adding.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option C

4. Quick Check:

   Safe mid calculation = low + (high - low)/2 [OK]

Hint: Use low + (high - low)/2 to avoid overflow [OK]

Common Mistakes:

• Using (low + high)/2 causing overflow
• Using subtraction incorrectly in mid calculation
• Multiplying low and high instead of adding

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

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);
    std::cout << result;
    return 0;
}

medium

A. 3

B. 4

C. -1

D. 2

Solution

1. Step 1: Trace the binary search calls

   Initial call: low=0, high=4, mid=2, arr[2]=6 matches target 6, so return 2.

2. Step 2: Return the index found

   Since arr[2] == 6, the function returns 2 immediately.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Check middle element first to find index quickly [OK]

Common Mistakes:

• Confusing index with value
• Not updating mid correctly
• Returning -1 when element is present

4. Find the error in the following binary search code snippet:

int binarySearch(int arr[], int low, int high, int x) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) low = mid;
        else high = mid - 1;
    }
    return -1;
}

medium

A. The update low = mid should be low = mid + 1.

B. The loop condition should be low < high.

C. The mid calculation can cause overflow.

D. The function should return mid + 1 instead of mid.

Solution

1. Step 1: Analyze the update of low pointer

   When arr[mid] < x, low should move to mid + 1 to avoid infinite loop.

2. Step 2: Identify the infinite loop cause

   Setting low = mid keeps low same if mid equals low, causing infinite loop.

3. Final Answer:

   The update low = mid should be low = mid + 1. -> Option A

4. Quick Check:

   Increment low past mid to avoid infinite loop [OK]

Hint: Increment low by 1 after mid when moving right [OK]

Common Mistakes:

• Not incrementing low causing infinite loop
• Using wrong loop condition
• Ignoring overflow in mid calculation

5. You have a sorted array with duplicate elements: {1, 2, 2, 2, 3, 4}. How can you modify binary search to find the first occurrence of 2?

hard

A. Return immediately when 2 is found.

B. Keep searching left half even after finding 2 to find first occurrence.

C. Search right half after finding 2 to find last occurrence.

D. Use linear search instead of binary search.

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any occurrence, not necessarily the first.

2. Step 2: Modify search to find first occurrence

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

3. Step 3: Stop when mid is first or left element is different

   Return mid if it is first element or previous element is different.

4. Final Answer:

   Keep searching left half even after finding 2 to find first occurrence. -> Option B

5. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: After match, move left to find first duplicate [OK]

Common Mistakes:

• Returning first found index without checking left
• Searching right half after finding target
• Using linear search unnecessarily