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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of iterative binary search on sorted array

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

DSA C

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

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

A 2

B 3

C -1

D 4

💡 Hint

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

The array is [1, 3, 5, 7, 9, 11]. The value 7 is at index 3 (0-based). The binary search returns the index where the value is found.

🧠 Conceptual

intermediate

Number of iterations in iterative binary search

If you perform iterative binary search on a sorted array of 16 elements, what is the maximum number of iterations the while loop will run?

A 5

B 8

C 16

D 4

💡 Hint

Each iteration halves the search space. Think about powers of 2.

Binary search halves the search space each iteration. For 16 elements, max iterations = log2(16) = 4.

🔧 Debug

advanced

Identify the error in this iterative binary search code

What error will this code produce when searching for 11 in the array?

DSA C

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

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, n, 11);
    printf("%d", result);
    return 0;
}

A Runtime error: Array index out of bounds

B Compilation error

C Returns 4 (correct index)

D Returns -1 (not found)

💡 Hint

Check the initial value of 'high' and how it is used to access array elements.

The variable 'high' is initialized to n, which is one past the last valid index. Accessing arr[mid] when mid equals n causes out-of-bounds access.

📝 Syntax

advanced

What error does this iterative binary search code produce?

What error will this code cause when compiled?

DSA C

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

A Syntax error: missing semicolon

B Runtime error: division by zero

C Logical error: infinite loop

D No error, runs correctly

💡 Hint

Look carefully at the line calculating 'mid'.

The line calculating 'mid' is missing a semicolon at the end, causing a syntax error during compilation.

🚀 Application

expert

Final index after iterative binary search modifications

Consider this iterative binary search variant that updates 'low' and 'high' differently. What is the final value of 'low' after the loop ends when searching for 6 in the array?

DSA C

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

int main() {
    int arr[] = {1, 3, 5, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = binarySearch(arr, n, 6);
    printf("%d", index);
    return 0;
}

A 4

B 2

C 3

D 5

💡 Hint

This variant finds the lower bound index of x. Trace the loop carefully.

The loop narrows down the search space until low == high, which is the index of the first element >= x. For x=6, that index is 3.

Practice

1. What is the main purpose of the while loop in the iterative binary search algorithm?

easy

A. To swap elements in the array

B. To sort the array before searching

C. To print all elements in the array

D. To repeatedly divide the search range until the target is found or range is empty

Solution

1. Step 1: Understand the role of the loop

   The while loop runs as long as the search range is valid, narrowing down the range by half each time.

2. Step 2: Identify the loop's goal

   The loop stops when the target is found or when the search range becomes empty, meaning the target is not present.

3. Final Answer:

   To repeatedly divide the search range until the target is found or range is empty -> Option D

4. Quick Check:

   Loop narrows search range until target found or range empty [OK]

Hint: Loop halves search range until target found or no range left [OK]

Common Mistakes:

• Thinking the loop sorts the array
• Assuming the loop swaps elements
• Believing the loop prints elements

2. Which of the following is the correct way to calculate the middle index in an iterative binary search in C 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 = (low * high) / 2;

Solution

1. Step 1: Understand overflow risk

   Adding low + high directly can overflow if both are large integers.

2. Step 2: Use safe middle calculation

   Calculating low + (high - low) / 2 avoids overflow by subtracting first.

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 middle calculation
• Multiplying indices which is wrong

3. What will be the output of the following C code snippet using iterative binary search?

int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int target = 6;
int low = 0, high = n - 1;
int mid;
while (low <= high) {
    mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        printf("%d", mid);
        break;
    } else if (arr[mid] < target) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

medium

A. 3

B. 2

C. 1

D. -1

Solution

1. Step 1: Trace the binary search steps

   Initial low=0, high=4, mid=2. arr[2]=6 matches target 6.

2. Step 2: Print the mid index

   Since arr[mid] == target, the code prints 2 and breaks the loop.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check mid index where target matches first [OK]

Common Mistakes:

• Confusing index with value
• Not updating low/high correctly
• Assuming target not found

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

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

medium

A. The loop condition should be while (low <= high)

B. The mid calculation causes overflow

C. The function returns mid instead of value

D. The array is not sorted before searching

Solution

1. Step 1: Analyze loop condition

   The loop uses while (low < high), which misses checking when low equals high.

2. Step 2: Correct loop condition

   It should be while (low <= high) to include the last element in search.

3. Final Answer:

   The loop condition should be while (low <= high) -> Option A

4. Quick Check:

   Loop must include low == high to check last element [OK]

Hint: Use <= in loop to check all elements including last [OK]

Common Mistakes:

• Using < instead of <= in loop condition
• Ignoring overflow in mid calculation (not here)
• Confusing return value with index
• Assuming array needs sorting inside function

5. Given a sorted array int arr[] = {1, 3, 5, 7, 9, 11, 13}, write the iterative binary search steps to find the target 10. What will be the final output of the search function?

hard

A. -1 (target not found)

B. Index 4

C. Index 5

D. Index 3

Solution

1. Step 1: Trace search for target 10

   Initial low=0, high=6, mid=3 (arr[3]=7). Since 7 < 10, low=mid+1=4.

2. Step 2: Continue search narrowing range

   Now low=4, high=6, mid=5 (arr[5]=11). Since 11 > 10, high=mid-1=4.

3. Step 3: Final check

   Now low=4, high=4, mid=4 (arr[4]=9). Since 9 < 10, low=mid+1=5. Now low=5 > high=4, loop ends.

4. Final Answer:

   -1 (target not found) -> Option A

5. Quick Check:

   Target 10 not in array, returns -1 [OK]

Hint: If target not found, binary search returns -1 [OK]

Common Mistakes:

• Assuming closest smaller element index is returned
• Not updating low/high correctly
• Stopping search too early