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 mid

↓

Repeat loop or exit if low > high

↓

Return -1 if not found

Start with low and high pointers on the sorted array. Repeatedly check middle element and adjust pointers until target is found or pointers cross.

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 a sorted array using an iterative binary search.

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Pointer Change	Visual State
1	Initialize low and high	0	6	-	-	-	Set low=0, high=6	[2,4,6,8,10,12,14]
2	Calculate mid	0	6	3	8	8 < 10?	low = mid + 1 = 4	[2,4,6,8,10,12,14]
3	Calculate mid	4	6	5	12	12 > 10?	high = mid - 1 = 4	[2,4,6,8,10,12,14]
4	Calculate mid	4	4	4	10	10 == 10?	Return mid=4	[2,4,6,8,10,12,14]

💡 Target found at index 4, loop ends.

Variable Tracker

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

Key Moments - 3 Insights

Why do we update 'low' to mid + 1 when arr[mid] < target?

Because arr[mid] is less than target, all elements before and including mid cannot be target, so we move low to mid + 1 to search the right half. See execution_table step 2.

Why does the loop stop when low > high?

When low passes high, it means the search space is empty and target is not found. The loop condition low <= high fails, ending the search. This is implied after step 4 if target not found.

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

Mid is the middle index between low and high to split the search space in half. This helps efficiently narrow down where the target could be. See mid values in execution_table steps 2-4.

Visual Quiz - 3 Questions

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

A 3

B 5

C 4

D 6

💡 Hint

Check the 'mid' column in execution_table row for step 3.

At which step does the pointer 'high' change to 4?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look at the 'Pointer Change' column in execution_table for when high is updated.

If the target was 7 instead of 10, what would happen at step 2?

A high would be set to mid - 1 = 2

B low would be set to mid + 1 = 4

C Return mid immediately

D Loop would end

💡 Hint

Compare arr[mid] = 8 with target 7 at step 2 in execution_table and see pointer changes.

Concept Snapshot

Binary Search Iterative Approach:
- Works on sorted arrays
- Use two pointers: low and high
- Calculate mid = (low + high) / 2
- Compare arr[mid] with target
- If equal, return mid
- If arr[mid] < target, move low to mid + 1
- Else move high to mid - 1
- Repeat until low > high
- Return -1 if not found

Full Transcript

Binary Search Iterative Approach starts with a sorted array and two pointers low and high. We calculate the middle index mid and compare the middle element with the target. If they match, we return mid. If the middle element is less than the target, we move low to mid + 1 to search the right half. If greater, we move high to mid - 1 to search the left half. We repeat this until low exceeds high, which means the target is not in the array. This approach efficiently narrows down the search space by half each step.