Binary Search Iterative Approach in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

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

DSA C++

#include <iostream>

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

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

A -1

B 4

C 2

D 3

💡 Hint

Remember that array indexing starts at 0 and binary search returns the index of the target if found.

The target 7 is at index 3 in the array {1, 3, 5, 7, 9, 11}. The binary search finds it and returns 3.

❓ Predict Output

intermediate

Result when target is not in array

What will be the output of the following C++ code when searching for the value 8 in the sorted array?

DSA C++

#include <iostream>

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

int main() {
    int arr[] = {2, 4, 6, 10, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = binarySearch(arr, n, 8);
    std::cout << index << std::endl;
    return 0;
}

A -1

B 2

C 3

D 0

💡 Hint

If the target is not found, the function returns -1.

Since 8 is not present in the array, the binary search completes without finding it and returns -1.

🧠 Conceptual

advanced

Understanding the Mid Calculation in Binary Search

Why is the middle index calculated as mid = left + (right - left) / 2 instead of mid = (left + right) / 2 in the iterative binary search?

A To ensure mid is always rounded up

B Because it is faster to compute

C To avoid integer overflow when left and right are large values

D To handle negative indices correctly

💡 Hint

Think about what happens if left and right are very large integers.

Using left + (right - left) / 2 prevents overflow that can happen if left + right exceeds the maximum integer value.

🔧 Debug

advanced

Identify the bug in this binary search code

What error will occur when running this binary search code?

DSA C++

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n;
    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 Array index out of bounds error

B Infinite loop

C No error, works correctly

D Compilation error due to missing return

💡 Hint

Check the initial value of right and how it relates to array indices.

The variable right is initialized to n, which is one past the last valid index (n-1). Accessing arr[mid] when mid equals n causes an out of bounds error.

🚀 Application

expert

Binary Search to Find First Occurrence of a Target

Given a sorted array with possible duplicates, which iterative binary search modification correctly returns the index of the first occurrence of the target value?

DSA C++

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

A The code above causes infinite loop for duplicates

B The code above correctly finds the first occurrence index

C The code above returns -1 even if target exists

D The code above finds the last occurrence index instead

💡 Hint

When target is found, move right pointer to mid - 1 to search left side.

By updating result and moving right to mid - 1, the code searches for earlier occurrences, ensuring the first occurrence is found.