Binary Search Iterative Approach in DSA C

Mental Model

Binary search finds a number by repeatedly cutting the search area in half until the number is found or no area remains.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is before or after that page, and repeating this until you find the word.

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Indexes:  0      1      2      3      4       5       6
Pointers:  ↑mid
           ↑low
                   ↑high

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], search for 9

Goal: Find the index of 9 in the array using iterative binary search

Step 1: Calculate mid index between low=0 and high=6

Array: 1 -> 3 -> 5 -> [7] -> 9 -> 11 -> 13 -> null
Indexes: 0    1    2    [3]   4    5    6
Pointers: low=0, mid=3, high=6

Why: We start by checking the middle element to decide which half to search next

Step 2: Compare mid value 7 with target 9; since 7 < 9, move low to mid+1=4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13 -> null
Indexes: 0    1    2    3    [4]   5    6
Pointers: low=4, high=6

Why: Target is greater than mid value, so search right half

Step 3: Calculate new mid between low=4 and high=6

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13 -> null
Indexes: 0    1    2    3    [4]   5    6
Pointers: low=4, mid=5, high=6

Why: Find new middle in the reduced search area

Step 4: Compare mid value 11 with target 9; since 11 > 9, move high to mid-1=4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13 -> null
Indexes: 0    1    2    3    [4]   5    6
Pointers: low=4, high=4

Why: Target is smaller than mid value, so search left half

Step 5: Calculate new mid between low=4 and high=4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13 -> null
Indexes: 0    1    2    3    [4]   5    6
Pointers: low=4, mid=4, high=4

Why: Find new middle in the reduced search area

Step 6: Compare mid value 9 with target 9; they are equal, return index 4

Array: 1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13 -> null
Indexes: 0    1    2    3    [4]   5    6
Pointers: found target at mid=4

Why: Target found at mid index

Result:

1 -> 3 -> 5 -> 7 -> [9] -> 11 -> 13 -> null
Target 9 found at index 4

Annotated Code

DSA C

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // find middle index
        if (arr[mid] == target) {
            return mid;  // target found
        } else if (arr[mid] < target) {
            low = mid + 1;  // search right half
        } else {
            high = mid - 1;  // search left half
        }
    }
    return -1;  // target not found
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int index = binary_search(arr, size, target);
    if (index != -1) {
        printf("Target %d found at index %d\n", target, index);
    } else {
        printf("Target %d not found in array\n", target);
    }
    return 0;
}

int mid = low + (high - low) / 2; // find middle index

calculate middle index to split search area

if (arr[mid] == target) { return mid; }

check if middle element is target

else if (arr[mid] < target) { low = mid + 1; }

target is greater, move low pointer to right half

else { high = mid - 1; }

target is smaller, move high pointer to left half

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by cutting search space repeatedly

Edge Cases

empty array

function returns -1 immediately as low > high

DSA C

while (low <= high) {

target smaller than all elements

search narrows and returns -1 after checking all possibilities

DSA C

while (low <= high) {

target larger than all elements

search narrows and returns -1 after checking all possibilities

DSA C

while (low <= high) {

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it cuts the search area in half each time.

Common Mistakes

Mistake: Calculating mid as (low + high) which can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly causing infinite loop
Fix: Ensure low = mid + 1 or high = mid - 1 to shrink search space

Summary

Finds the position of a target value in a sorted array by repeatedly halving the search range.

Use when you have a sorted list and want to find an element efficiently.

The key is to compare the middle element and decide which half to search next.

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