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

↓

If not found, return -1

Start with low and high pointers on the sorted array ends, repeatedly check middle element, adjust pointers based on comparison until target is found or pointers cross.

Execution Sample

DSA C#

int BinarySearch(int[] arr, int target) {
  int low = 0, high = arr.Length - 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;
}

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

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Pointer Changes	Visual State
1	Initialize low and high	0	6	-	-	-	low=0, high=6	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 == 9? No	None	[1, 3, 5, 7, 9, 11, 13]
3	Compare arr[mid] < target	0	6	3	7	7 < 9? Yes	low = mid + 1 = 4	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	6	5	11	11 == 9? No	None	[1, 3, 5, 7, 9, 11, 13]
5	Compare arr[mid] > target	4	6	5	11	11 > 9? Yes	high = mid - 1 = 4	[1, 3, 5, 7, 9, 11, 13]
6	Calculate mid	4	4	4	9	9 == 9? Yes	Return mid = 4	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 4, loop ends.

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]	-	7	7	11	11	9	9

Key Moments - 3 Insights

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

Because arr[mid] is less than target, the target must be in the right half, so we move 'low' just after 'mid' to exclude mid and left side (see Step 3 in execution_table).

Why do we update 'high' to mid - 1 when arr[mid] > target?

Because arr[mid] is greater than target, the target must be in the left half, so we move 'high' just before 'mid' to exclude mid and right side (see Step 5 in execution_table).

Why does the loop stop when low > high?

When 'low' passes 'high', it means the search space is empty and target is not found, so we exit and return -1 (not shown in this example as target was found).

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 for Step 4.

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

A Step 4

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Pointer Changes' column and 'high' value in execution_table.

If the target was 12 instead of 9, what would happen to 'low' after Step 3?

A low would be set to 4

B low would be set to 6

C low would be set to 5

D low would remain 0

💡 Hint

Consider how 'low' updates when arr[mid] < target, see Step 3.

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
- If arr[mid] > target, 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 at start and high at end. We calculate the middle index and compare the middle element with the target. If they match, we return the index. If the middle element is less than the target, we move the low pointer just after mid to search the right half. If greater, we move the high pointer just before mid to search the left half. This repeats until low pointer passes high pointer, meaning the target is not in the array. The example traced shows searching for 9 in [1,3,5,7,9,11,13], finding it at index 4 after adjusting pointers twice.

Practice

1. What is the main purpose of the Binary Search Iterative Approach in a sorted array?

easy

A. To find the maximum value in the array

B. To sort the array elements in ascending order

C. To reverse the array elements

D. To find the position of a target value efficiently by repeatedly dividing the search interval in half

Solution

1. Step 1: Understand binary search goal

   Binary search aims to find a target value's position quickly by checking the middle element and narrowing the search range.

2. Step 2: Identify iterative approach

   The iterative method uses a loop to repeatedly divide the search interval until the target is found or the interval is empty.

3. Final Answer:

   To find the position of a target value efficiently by repeatedly dividing the search interval in half -> Option D

4. Quick Check:

   Binary search = efficient target search [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Confusing binary search with sorting
• Thinking it reverses the array
• Assuming it finds max value

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 - low) / 2;

B. int mid = (low + high) / 2;

C. int mid = (low - high) / 2;

D. int mid = (low * high) / 2;

Solution

1. Step 1: Understand overflow risk

   Adding low and high directly can cause integer overflow if values are large.

2. Step 2: Use safe middle calculation

   Calculating mid as low + (high - low) / 2 avoids overflow by subtracting before adding.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option A

4. Quick Check:

   Safe mid calculation = low + (high - low) / 2 [OK]

Hint: Use low + (high - low) / 2 to prevent overflow [OK]

Common Mistakes:

• Using (low + high) / 2 causing overflow
• Subtracting incorrectly in mid calculation
• Multiplying indices instead of adding

3. What will be the output of the following C# code snippet?

int[] arr = {2, 4, 6, 8, 10};
int target = 6;
int low = 0, high = arr.Length - 1;
int result = -1;
while (low <= high) {
  int mid = low + (high - low) / 2;
  if (arr[mid] == target) {
    result = mid;
    break;
  } else if (arr[mid] < target) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}
Console.WriteLine(result);

medium

A. -1

B. 3

C. 2

D. 0

Solution

1. Step 1: Trace the binary search steps

   Initial low=0, high=4, mid=2 (element 6). arr[2] == target 6, so result=2 and loop breaks.

2. Step 2: Output the result

   Since target found at index 2, Console.WriteLine prints 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check middle element first to find target quickly [OK]

Common Mistakes:

• Confusing index with value
• Not updating low or high correctly
• Assuming target not found returns 0

4. Identify the error in the following iterative binary search code snippet and choose the correct fix:

int BinarySearch(int[] arr, int target) {
  int low = 0, high = arr.Length - 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. Change while condition to 'while (low <= high)'

B. Change mid calculation to '(low + high) / 2'

C. Remove 'return -1;' at the end

D. Change 'low = mid + 1;' to 'low = mid - 1;'

Solution

1. Step 1: Analyze loop condition

   The loop uses 'while (low < high)', which misses checking when low equals high, possibly skipping the last element.

2. Step 2: Correct loop condition

   Changing to 'while (low <= high)' ensures all elements are checked including when low equals high.

3. Final Answer:

   Change while condition to 'while (low <= high)' -> Option A

4. Quick Check:

   Loop must include low == high to check all elements [OK]

Hint: Use <= in loop to include last element check [OK]

Common Mistakes:

• Using < instead of <= in loop condition
• Incorrect mid calculation causing overflow
• Wrong update of low or high pointers

5. Given a sorted array with possible duplicate elements, how can you modify the iterative binary search to find the first occurrence of a target value?

hard

A. Return immediately when target is found

B. When target is found, continue searching left half to find earlier occurrence

C. Search only the right half after finding target

D. Use linear search instead of binary search

Solution

1. Step 1: Understand duplicates in sorted array

   Duplicates mean target can appear multiple times; we want the first index where it appears.

2. Step 2: Modify binary search to find first occurrence

   When target found at mid, record mid but continue searching left half (high = mid - 1) to find earlier occurrence.

3. Final Answer:

   When target is found, continue searching left half to find earlier occurrence -> Option B

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: On match, move left to find first occurrence [OK]

Common Mistakes:

• Stopping search immediately on first match
• Searching right half after finding target
• Switching to linear search unnecessarily