Why Binary Search and What Sorted Order Gives You in DSA C++ - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

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

DSA C++

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    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;
}

#include <iostream>
int main() {
    int arr[] = {2, 4, 6, 8, 10, 12};
    int index = binarySearch(arr, 6, 8);
    std::cout << index << 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 target if found.

The target 8 is at index 3 in the sorted array. Binary search finds it and returns the index.

🧠 Conceptual

intermediate

Why Must the Array Be Sorted for Binary Search?

Why is it necessary for the array to be sorted before applying binary search?

A Because binary search requires the array to be sorted in descending order only.

B Because binary search only works on arrays with unique elements.

C Because binary search compares the target with the middle element to decide which half to search next, which only works if the array is sorted.

D Because binary search can only be applied to arrays of even length.

💡 Hint

Think about how binary search decides which half of the array to search next.

Binary search relies on the order of elements to eliminate half of the search space each time. Without sorting, this logic fails.

❓ Predict Output

advanced

Result of Binary Search on Unsorted Array

What will be the output of this C++ code that runs binary search on an unsorted array?

DSA C++

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    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;
}

#include <iostream>
int main() {
    int arr[] = {10, 2, 8, 4, 12, 6};
    int index = binarySearch(arr, 6, 4);
    std::cout << index << std::endl;
    return 0;
}

A -1

B 0

C 3

D 2

💡 Hint

Binary search assumes sorted order. What happens if the array is not sorted?

Since the array is not sorted, binary search may not find the target correctly and returns -1 indicating not found.

🔧 Debug

advanced

Identify the Bug in Binary Search Implementation

What is the bug in this binary search code that causes it to fail for some inputs?

DSA C++

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    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;
}

A The condition in the while loop should be 'left < right' instead of 'left <= right'.

B The 'right' variable should be initialized to 'size - 1' instead of 'size'.

C The 'left' variable should be initialized to 1 instead of 0.

D The mid calculation should be 'mid = (left + right) / 2 + 1'.

💡 Hint

Check the valid index range for the array.

Array indices go from 0 to size-1. Initializing 'right' to 'size' causes out-of-bound access.

🧠 Conceptual

expert

Why Binary Search is More Efficient Than Linear Search on Sorted Data

Why is binary search more efficient than linear search when the data is sorted?

A Because binary search sorts the array first, then searches linearly.

B Because binary search checks every element sequentially but faster due to sorting.

C Because binary search uses hashing to find elements instantly.

D Because binary search divides the search space in half each step, reducing the number of comparisons to logarithmic time.

💡 Hint

Think about how many elements are left to check after each step in binary search.

Binary search cuts the search space in half each time, leading to O(log n) time, much faster than linear search's O(n).