Binary Search Iterative Approach in DSA C - Execution Trace

Concept Flow - Binary Search Iterative Approach

Start with sorted array and target

↓

Set low = 0, high = array_length - 1

↓

While low <= high

↓

Calculate mid = (low + high) / 2

↓

Compare array[mid

↓

Equal

↓

Return

↓

Repeat while loop

↓

Not found

↓

Return -1

This flow shows how binary search narrows down the search range by adjusting low and high pointers until the target is found or the range is empty.

Execution Sample

DSA C

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;
}

This code searches for target in sorted array arr using an iterative binary search and returns the index or -1 if not found.

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Action	Search Range Visual
1	Initialize low and high	0	6	-	-	-	Start search	[2,4,6,8,10,12,14] (full array)
2	Calculate mid	0	6	3	8	8 == 10?	No	[2,4,6,8,10,12,14]
3	Compare arr[mid] < target	0	6	3	8	8 < 10?	Yes, low = mid+1 = 4	[10,12,14] (index 4 to 6)
4	Calculate mid	4	6	5	12	12 == 10?	No	[10,12,14]
5	Compare arr[mid] < target	4	6	5	12	12 < 10?	No, high = mid-1 = 4	[10] (index 4 to 4)
6	Calculate mid	4	4	4	10	10 == 10?	Yes, return 4	[10]
7	End	4	4	4	10	-	Target found at index 4	[10]

💡 Search ends when target is found at index 4 or when low > high (not in this case).

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
low	0	0	4	4	4	4	4
high	6	6	6	6	4	4	4
mid	-	3	3	5	5	4	4
arr[mid]	-	8	8	12	12	10	10

Key Moments - 3 Insights

Why do we update low to mid + 1 when arr[mid] is less than target?

Because arr[mid] is smaller than target, the target must be in the right half. So we move low to mid + 1 to search only the right side (see step 3 in execution_table).

Why do we stop the loop when low > high?

When low becomes greater than high, it means the search range is empty and the target is not in the array (not shown in this example but implied by the loop condition).

Why do we calculate mid as (low + high) / 2 each time?

Because mid is the middle index of the current search range, recalculated each iteration to split the range in half (see steps 2, 4, 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of mid at step 4?

A 3

B 4

C 5

D 6

💡 Hint

Check the 'mid' column in execution_table row with Step 4.

At which step does the search range reduce to a single element?

A Step 3

B Step 5

C Step 6

D Step 2

💡 Hint

Look at the 'Search Range Visual' column to see when only one element remains.

If the target was 7 instead of 10, what would happen to the value of low after step 3?

A It would stay 0

B It would become 4

C It would become 3

D It would become 5

💡 Hint

At step 3, arr[mid]=8 > 7, so arr[mid] < target is false; take else branch (high = mid - 1), low unchanged (stays 0).

Concept Snapshot

Binary Search Iterative Approach:
- Works on sorted arrays.
- Use two pointers: low and high.
- Calculate mid = (low + high) / 2 each loop.
- If arr[mid] == target, return mid.
- If arr[mid] < target, move low to mid + 1.
- Else, move high to mid - 1.
- Stop when low > high (target not found).

Full Transcript

Binary Search Iterative Approach searches a sorted array by repeatedly dividing the search range in half. It starts with low at 0 and high at the last index. Each step calculates mid as the middle index. If the middle element equals the target, it returns the index. If the middle element is less than the target, it moves low to mid + 1 to search the right half. Otherwise, it moves high to mid - 1 to search the left half. The loop continues until low exceeds high, meaning the target is not found. This method efficiently narrows down the search range to find the target or conclude it is absent.

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