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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search Call

What is the output of the following C code snippet that performs a recursive binary search on a sorted array?

Assume the array is sorted in ascending order.

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, 8, 10, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    printf("%d", result);
    return 0;
}

A 4

B 3

C -1

D 5

💡 Hint

Remember array indexing starts at 0. Find the position of 10 in the array.

The array is {2,4,6,8,10,12,14}. The element 10 is at index 4 (0-based). The binary search returns the index where the element is found.

🧠 Conceptual

intermediate

Divide and Conquer Principle in Binary Search

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

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

B It divides the array into multiple parts and searches all parts simultaneously.

C It searches the entire array linearly after dividing it into halves.

D It combines all elements before searching for the target.

💡 Hint

Think about how binary search reduces the search space each step.

Binary search splits the array into two halves and only continues searching the half where the target could be, reducing the problem size each time.

❓ Predict Output

advanced

Output of Iterative Binary Search with Missing Element

What is the output of the following iterative binary search code when searching for 7 in the given array?

DSA C

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

int main() {
    int arr[] = {1, 3, 5, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 7;
    int result = binarySearchIter(arr, n, x);
    printf("%d", result);
    return 0;
}

A 0

B 2

C 3

D -1

💡 Hint

7 is not in the array. What does the function return when the element is not found?

Since 7 is not present in the array, the binary search returns -1 indicating the element is not found.

🔧 Debug

advanced

Identify the Logical Error in Binary Search

Consider this binary search code snippet. What logical error causes it to fail for some inputs?

DSA C

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

A The base case condition should be 'left >= right' instead of 'left > right'.

B The recursive call uses 'mid' instead of 'mid + 1' when searching the right half, causing infinite recursion.

C The mid calculation should be 'left - right' instead of 'left + right'.

D The function should return 'left' instead of '-1' when element is not found.

💡 Hint

Check how the search space changes in recursive calls.

Using 'mid' instead of 'mid + 1' when searching the right half causes the same middle index to be searched repeatedly, leading to infinite recursion.

🧠 Conceptual

expert

Time Complexity of Binary Search in Worst Case

What is the worst-case time complexity of binary search on a sorted array of size n, and why?

A O(1), because it directly jumps to the middle element.

B O(n), because it may need to check every element.

C O(log n), because the search space halves with each step.

D O(n log n), because it divides and sorts the array first.

💡 Hint

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

Binary search halves the search space each step, so it takes about log base 2 of n steps in the worst case.