Binary Search vs Linear Search Real Cost Difference in DSA C++ - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linear Search on Sorted Array

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

DSA C++

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) return i;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = linearSearch(arr, n, 7);
    if (index != -1) {
        std::cout << "Found at index " << index << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}

A Found at index 3

B Found at index 2

C Not found

D Found at index 4

💡 Hint

Remember that array indexing starts at 0 and linear search checks elements one by one.

The value 7 is at the 4th position in the array, which is index 3 (0-based). Linear search finds it and returns index 3.

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

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

DSA C++

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

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = binarySearch(arr, 0, n - 1, 7);
    if (index != -1) {
        std::cout << "Found at index " << index << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}

A Found at index 2

B Found at index 4

C Not found

D Found at index 3

💡 Hint

Binary search divides the search space in half each step.

The value 7 is at index 3. Binary search finds it by checking the middle element and narrowing down the search.

🧠 Conceptual

advanced

Time Complexity Comparison

Which statement correctly compares the time complexity of linear search and binary search on a sorted array of size n?

A Both linear and binary search are O(n)

B Linear search is O(log n), binary search is O(n)

C Linear search is O(n), binary search is O(log n)

D Both linear and binary search are O(log n)

💡 Hint

Think about how many elements each algorithm checks in the worst case.

Linear search checks each element one by one, so it takes O(n). Binary search halves the search space each time, so it takes O(log n).

🚀 Application

advanced

Choosing Search Method for Unsorted Data

You have a large unsorted array and need to find if a value exists. Which search method is best and why?

A Sort the array first then use linear search

B Use linear search because binary search requires sorted data

C Use binary search because it is always faster

D Use binary search without sorting because it works on any array

💡 Hint

Binary search needs sorted data to work correctly.

Binary search only works on sorted arrays. For unsorted data, linear search is the correct choice without extra steps.

🔧 Debug

expert

Why Does This Binary Search Fail?

What error or problem does the following binary search code have when searching for 7 in the array {1, 3, 5, 7, 9, 11}? int binarySearch(int arr[], int left, int right, int x) { while (left < right) { int mid = (left + right) / 2; if (arr[mid] == x) return mid; if (arr[mid] < x) left = mid + 1; else right = mid - 1; } return -1; } int main() { int arr[] = {1, 3, 5, 7, 9, 11}; int n = sizeof(arr) / sizeof(arr[0]); int index = binarySearch(arr, 0, n - 1, 7); if (index != -1) { std::cout << "Found at index " << index << std::endl; } else { std::cout << "Not found" << std::endl; } return 0; }

A It may miss the target because the loop condition excludes right boundary

B It causes an infinite loop due to incorrect mid calculation

C It always returns -1 even if the element is present

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

💡 Hint

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

The loop uses 'while (left < right)', so when left == right, the loop stops without checking that element. This can cause missing the target if it is at the right boundary.