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.

Practice

1. What is the main purpose of the binarySearchIterative function in the iterative binary search approach?

easy

A. To find the position of a target value in a sorted array

B. To sort an unsorted array

C. To reverse the elements of an array

D. To count the number of elements in an array

Solution

1. Step 1: Understand the function goal

   The binary search function is designed to locate a target value within a sorted array efficiently.

2. Step 2: Identify the operation performed

   It repeatedly divides the search interval in half to find the target's position or determine it is not present.

3. Final Answer:

   To find the position of a target value in a sorted array -> Option A

4. Quick Check:

   Binary search locates target index [OK]

Hint: Binary search finds target index in sorted array fast [OK]

Common Mistakes:

• Thinking binary search sorts the array
• Confusing binary search with linear search
• Assuming it works on unsorted arrays

2. Which of the following is the correct syntax to calculate the middle index in an iterative binary search to avoid overflow?

easy

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

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

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

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

Solution

1. Step 1: Understand overflow risk in mid calculation

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

2. Step 2: Use safe formula to avoid overflow

   The formula low + (high - low) / 2 calculates mid without adding large numbers directly.

3. Final Answer:

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

4. Quick Check:

   Safe mid calculation avoids overflow [OK]

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

Common Mistakes:

• Using (low + high)/2 causing overflow
• Subtracting incorrectly in mid calculation
• Mixing up low and high in formula

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

int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int target = 6;
int result = binarySearchIterative(arr, n, target);
std::cout << result << std::endl;

// Assume binarySearchIterative is correctly implemented iterative binary search

medium

A. -1

B. 2

C. 3

D. 1

Solution

1. Step 1: Identify the target and array

   The array is {2, 4, 6, 8, 10} and the target is 6.

2. Step 2: Find the index of target using binary search

   6 is at index 2 (0-based indexing) in the array.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Remember array indexing starts at 0 [OK]

Common Mistakes:

• Confusing index with value
• Using 1-based indexing instead of 0-based
• Assuming target not found returns 0

4. Identify the error in the following iterative binary search code snippet:

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

medium

A. The mid calculation can cause integer overflow

B. The loop condition should be low < high

C. The return value should be 0 when not found

D. The array should be unsorted for binary search

Solution

1. Step 1: Review mid calculation

   Mid is calculated as (low + high) / 2 which can overflow if low and high are large.

2. Step 2: Suggest safer mid calculation

   Use low + (high - low) / 2 to avoid overflow in mid calculation.

3. Final Answer:

   The mid calculation can cause integer overflow -> Option A

4. Quick Check:

   Mid calculation overflow risk = true [OK]

Hint: Use safe mid formula to avoid overflow [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Returning 0 instead of -1 when not found
• Assuming binary search works on unsorted arrays

5. Given a sorted array arr = {1, 3, 5, 7, 9, 11, 13}, how many iterations will the iterative binary search take to find the target value 7?

hard

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Initialize low and high pointers

   low = 0, high = 6 (array length - 1)

2. Step 2: Trace each iteration to find 7

   Iteration 1: mid = 0 + (6-0)/2 = 3, arr[3] = 7 (target found at first check)

3. Step 3: Count iterations

   Only 1 iteration is needed because target is found immediately at mid index 3.

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Target found at first mid check [OK]

Hint: Count mid calculations until target found [OK]

Common Mistakes:

• Assuming always 3 iterations for any search
• Counting array length instead of iterations
• Forgetting zero-based indexing