Binary Search as Divide and Conquer in DSA C# - Execution Trace

Concept Flow - Binary Search as Divide and Conquer

Start with sorted array and target

↓

Calculate middle index

↓

Compare middle element with target

↓

Equal?

↓

Is target < middle element?

↓

Return index

↓

Repeat steps

Binary search splits the sorted array into halves, compares the middle element with the target, and recursively searches the correct half until the target is found or the search space is empty.

Execution Sample

DSA C#

int BinarySearch(int[] arr, int target) {
  int left = 0, right = arr.Length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

This code searches for 'target' in a sorted array 'arr' by repeatedly dividing the search range in half.

Execution Table

Step	Operation	Left	Right	Mid	arr[Mid]	Comparison	Action	Search Range Visual
1	Initialize	0	6	-	-	-	Start search	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 == 9? No	7 < 9, move left to mid+1=4	[7, 9, 11, 13] (indices 3 to 6)
3	Update left	4	6	-	-	-	Search right half	[9, 11, 13] (indices 4 to 6)
4	Calculate mid	4	6	5	11	11 == 9? No	11 > 9, move right to mid-1=4	[9, 11] (indices 4 to 5)
5	Update right	4	4	-	-	-	Search left half	[9] (index 4)
6	Calculate mid	4	4	4	9	9 == 9? Yes	Return index 4	[9] (index 4)
7	End	-	-	-	-	-	Target found at index 4	[9] (index 4)

💡 Search ends when target is found at index 4 or search range is empty.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	4	4	4	4	4
right	6	6	6	4	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 calculate mid as left + (right - left) / 2 instead of (left + right) / 2?

Calculating mid as left + (right - left) / 2 prevents integer overflow when left and right are large, as shown in Step 2 and Step 4 where mid is safely computed.

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

Because if arr[mid] is less than target, the target must be in the right half, so we move left to mid + 1 to exclude mid and all elements before it, as seen in Step 2 and Step 3.

What happens when left becomes greater than right?

When left > right, the search range is empty, meaning the target is not in the array. The loop ends and -1 is returned, but in this example, the target was found before that, as shown in Step 7.

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 the execution_table at Step 4.

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

A Step 5

B Step 3

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 12 instead of 9, what would happen at Step 4?

A Right would move to mid - 1

B Left would move to mid + 1

C Target found at mid

D Search ends immediately

💡 Hint

Check the 'Comparison' and 'Action' columns at Step 4 for how the search range changes.

Concept Snapshot

Binary Search divides a sorted array into halves.
Calculate mid = left + (right - left) / 2.
Compare arr[mid] with target.
If equal, return mid.
If target > arr[mid], search right half (left = mid + 1).
If target < arr[mid], search left half (right = mid - 1).
Repeat until found or range empty.

Full Transcript

Binary Search is a method to find a target value in a sorted array by repeatedly dividing the search range in half. We start with the full array and calculate the middle index safely using left + (right - left) / 2 to avoid overflow. We compare the middle element with the target. If they match, we return the index. If the target is greater, we move the left boundary to mid + 1 to search the right half. If smaller, we move the right boundary to mid - 1 to search the left half. This process repeats until the target is found or the search range is empty, meaning the target is not present. The execution table shows each step with the current left, right, mid, and the array segment being searched, helping visualize how the search narrows down quickly.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It repeatedly divides the search interval in half to find the target value.

B. It checks every element one by one until it finds the target.

C. It sorts the array before searching for the target.

D. It uses a queue to store elements during the search.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the array into two halves and decides which half to search next.

2. Step 2: Identify the repeated halving process

   It keeps dividing the search space by half until the target is found or no elements remain.

3. Final Answer:

   It repeatedly divides the search interval in half to find the target value. -> Option A

4. Quick Check:

   Divide and conquer = repeated halving [OK]

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

Common Mistakes:

• Thinking binary search checks every element
• Confusing binary search with linear search
• Assuming binary search sorts the array

2. Which of the following is the correct C# syntax to calculate the middle index in 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 = (low * high) / 2;

Solution

1. Step 1: Understand overflow risk in mid calculation

   Adding low and high directly can overflow if both are large.

2. Step 2: Use safe formula to avoid overflow

   Calculating mid as low + (high - low) / 2 prevents overflow by subtracting first.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use low + (high - low) / 2 to avoid 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. 3

B. 2

C. -1

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 B

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value first to find target quickly [OK]

Common Mistakes:

• Confusing index with value
• Not updating low and high correctly
• Assuming target not found and returning -1

4. Identify the bug in this binary search code snippet and select 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. Return 'low' instead of '-1' when target not found.

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

C. Remove 'else' before 'high = mid - 1;' to fix logic.

D. Change while condition to 'low <= high' to include last element.

Solution

1. Step 1: Analyze the loop condition

   The condition 'low < high' misses checking when low equals high, possibly skipping last element.

2. Step 2: Fix loop to include all elements

   Changing condition to 'low <= high' ensures the last element is checked.

3. Final Answer:

   Change while condition to 'low <= high' to include last element. -> Option D

4. Quick Check:

   Loop condition must cover all indices [OK]

Hint: Use 'low <= high' to cover full search range [OK]

Common Mistakes:

• Using 'low < high' and missing last element
• Changing mid calculation unnecessarily
• Returning wrong index when not found

5. You have a sorted array with duplicate values: int[] arr = {1, 2, 2, 2, 3, 4}. How would you modify binary search to find the first occurrence of 2?

hard

A. After finding target, continue searching left half to find first occurrence.

B. Return the first found index immediately without further checks.

C. Search the right half after finding target to find last occurrence.

D. Use linear search instead of binary search for duplicates.

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any occurrence, not necessarily the first.

2. Step 2: Modify search to find first occurrence

   When target found, move high pointer to mid - 1 to check left side for earlier occurrence, keep track of current mid.

3. Final Answer:

   After finding target, continue searching left half to find first occurrence. -> Option A

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: Keep searching left half after finding target for first occurrence [OK]

Common Mistakes:

• Stopping at first found index ignoring duplicates
• Searching right half instead of left for first occurrence
• Using linear search unnecessarily