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

↓

Find middle element

↓

Compare middle with target

↓

Found target

↓

Search left half

↓

Repeat until found or empty

Binary search repeatedly divides the sorted array in half, comparing the middle element to the target, and narrowing the search to left or right half until the target is found or the search space is empty.

Execution Sample

DSA C

int binarySearch(int arr[], int left, int right, int target) {
  if (right >= left) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
    return binarySearch(arr, mid + 1, right, target);
  }
  return -1;
}

This code searches for target in sorted array arr using divide and conquer by checking middle and recursing on half.

Execution Table

Step	Operation	Left Index	Right Index	Mid Index	Mid Value	Comparison	Next Range	Visual State
1	Start search	0	6	-	-	-	0 to 6	[2, 4, 6, 8, 10, 12, 14]
2	Calculate mid	0	6	3	8	8 vs 10 (target)	4 to 6	[2, 4, 6, 8, 10, 12, 14]
3	Calculate mid	4	6	5	12	12 vs 10 (target)	4 to 4	[2, 4, 6, 8, 10, 12, 14]
4	Calculate mid	4	4	4	10	10 vs 10 (target)	Found target	[2, 4, 6, 8, 10, 12, 14]
5	Return index	-	-	-	-	-	-	4

💡 Target found at index 4 on step 4; search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
left	0	0	4	4	-
right	6	6	6	4	-
mid	-	3	5	4	-
mid_value	-	8	12	10	-

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 steps 2-4 where mid is safely computed.

Why does the search stop when left > right?

When left > right, the search space is empty, meaning the target is not in the array. This is the base case that returns -1, as shown in step 5.

Why do we recurse on mid - 1 or mid + 1 instead of mid?

Because mid has already been checked and is not the target, we exclude it from the next search range to avoid infinite loops, as seen in steps 3 and 4.

Visual Quiz - 3 Questions

Look at the execution table, what is the mid value at step 3?

A 8

B 12

C 10

D 6

💡 Hint

Check the 'Mid Value' column in row for step 3.

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

A Step 4

B Step 1

C Step 3

D Step 2

💡 Hint

Look at 'Left Index' and 'Right Index' columns to find when they are equal.

If the target was 7 instead of 10, what would be the next search range after step 2?

A 3 to 6

B 4 to 6

C 0 to 2

D 0 to 3

💡 Hint

Compare mid value 8 with target 7 and see which half is searched next in step 2.

Concept Snapshot

Binary Search divides a sorted array by checking the middle element.
If middle equals target, return index.
If target < middle, search left half.
If target > middle, search right half.
Repeat until found or range empty.
Efficient O(log n) search method.

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 find the middle element. If the middle element equals the target, we return its index. If the target is smaller, we search the left half; if larger, the right half. This process repeats until the target is found or the search range is empty, which means the target is not present. The key steps include calculating the middle index safely to avoid overflow, comparing the middle value with the target, and adjusting the search range accordingly. This divide and conquer approach runs in logarithmic time, making it very efficient for large sorted arrays.

Practice

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

easy

A. It searches every element one by one until the target is found.

B. It divides the search range in half each time to find the target efficiently.

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

D. It uses recursion to add all elements in the array.

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 efficiency of halving the search space

   By halving the search space each time, it quickly narrows down the target location.

3. Final Answer:

   It divides the search range in half each time to find the target efficiently. -> Option B

4. Quick Check:

   Divide and conquer = halving search space [OK]

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

Common Mistakes:

• Thinking binary search checks every element
• Confusing binary search with sorting
• Believing binary search sums elements

2. Which of the following is the correct syntax to calculate the middle index in binary search in C?

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 safe middle index calculation

   Using low + (high - low) / 2 prevents integer overflow when low and high are large.

2. Step 2: Compare with other options

   int mid = (low + high) / 2; can overflow if low + high exceeds integer limit; options B and C are incorrect formulas.

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 low and high instead of adding

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

int arr[] = {2, 4, 6, 8, 10};
int low = 0, high = 4, target = 6;
while (low <= high) {
  int 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. 2

B. 3

C. 1

D. 4

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 A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Check mid index value matches target first [OK]

Common Mistakes:

• Not updating low and high correctly
• Confusing index with value
• Off-by-one errors in mid calculation

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

int binarySearch(int arr[], int low, int high, int target) {
  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 low <= high

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

C. Remove else if and use only if statements

D. Return 0 instead of -1 when not found

Solution

1. Step 1: Analyze the loop condition

   The loop uses while (low < high), which misses checking when low equals high.

2. Step 2: Correct the loop condition

   Changing to while (low <= high) ensures the last element is checked.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use while(low <= high) to include all elements [OK]

Common Mistakes:

• Using < instead of <= in loop condition
• Incorrect mid calculation causing overflow
• Returning wrong value when target not found

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

hard

A. Use linear search instead of binary search.

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

C. Search only the right half after finding the target.

D. After finding target, continue searching left half to find earlier occurrence.

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

   After finding target at mid, continue searching left half to check for earlier occurrences.

3. Final Answer:

   After finding target, continue searching left half to find earlier occurrence. -> Option D

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: Search left half after match to find first occurrence [OK]

Common Mistakes:

• Stopping at first found index ignoring duplicates
• Searching right half instead of left after match
• Switching to linear search unnecessarily