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.

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