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

↓

Set low = 0, high = array_size - 1

↓

Calculate mid = (low + high) / 2

↓

Compare array[mid

↓

Equal

↓

Return mid

↓

Repeat until low > high

↓

Return -1 (not found)

Binary search divides the sorted array into halves, compares the middle element with the target, and narrows the search range until the target is found or the range is empty.

Execution Sample

DSA C++

int binarySearch(int arr[], int low, int high, int target) {
  if (low > high) return -1;
  int mid = low + (high - low) / 2;
  if (arr[mid] == target) return mid;
  else if (target < arr[mid]) return binarySearch(arr, low, mid - 1, target);
  else return binarySearch(arr, mid + 1, high, target);
}

This recursive binary search function looks for target in a sorted array by dividing the search range in half each step.

Execution Table

Step	Operation	Low	High	Mid	Compare arr[mid] with target	Action	Array State (Visual)
1	Start search	0	6	-	-	Calculate mid	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	arr[3]=7 vs target=9	target > arr[mid], set low=mid+1=4	[1, 3, 5, 7, 9, 11, 13]
3	Calculate mid	4	6	5	arr[5]=11 vs target=9	target < arr[mid], set high=mid-1=4	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	4	4	arr[4]=9 vs target=9	Found target, return index 4	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	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
target	9	9	9	9	9

Key Moments - 3 Insights

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

Because arr[mid] is less than target, so the target can only be in the right half beyond mid. See execution_table step 2 where low changes from 0 to 4.

Why do we stop searching when low > high?

Because it means the search range is empty and the target is not in the array. This is the base case in the code and ensures termination.

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

To find the middle index of the current search range, dividing the array into two halves for the next step. This is shown 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 condition low > high become false, ending the search?

A Step 4

B Step 1

C Step 3

D The search never ends

💡 Hint

Look at the 'Low' and 'High' values in execution_table and see when the target is found.

If the target was 6 instead of 9, how would the 'low' variable change at step 2?

A low would become 4

B low would become 3

C low would remain 0

D low would become 5

💡 Hint

Compare target with arr[mid] at step 2 and see which branch is taken.

Concept Snapshot

Binary Search (Divide and Conquer):
- Works on sorted arrays
- Calculate mid = (low + high) / 2
- Compare arr[mid] with target
- If equal, return mid
- If target < arr[mid], search left half (high = mid - 1)
- Else search right half (low = mid + 1)
- Repeat until low > high (not found)

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 low and high pointers at the start and end of the array. We calculate the middle index mid and compare the middle element with the target. If they match, we return the index. If the target is smaller, we move the high pointer to mid - 1 to search the left half. If the target is larger, we move the low pointer to mid + 1 to search the right half. This process repeats until the target is found or the search range is empty (low > high), which means the target is not in the array.

Practice

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

easy

A. It divides the search space into two halves and discards one half each time.

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

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

D. It uses recursion to add elements to 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 continue searching based on the middle element.

2. Step 2: Identify the main action in binary search

   It discards the half where the target cannot be, reducing the search space quickly.

3. Final Answer:

   It divides the search space into two halves and discards one half each time. -> Option A

4. Quick Check:

   Divide and conquer = split and discard half [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 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 why to avoid overflow

   Using (low + high) / 2 can cause overflow if low and high are large integers.

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 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
• Using subtraction incorrectly in mid calculation
• Multiplying low and high instead of adding

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

int binarySearch(int arr[], int low, int high, int x) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == x) return mid;
    else if (arr[mid] > x) return binarySearch(arr, low, mid - 1, x);
    else return binarySearch(arr, mid + 1, high, x);
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = 5;
    int result = binarySearch(arr, 0, n - 1, 6);
    std::cout << result;
    return 0;
}

medium

A. 3

B. 4

C. -1

D. 2

Solution

1. Step 1: Trace the binary search calls

   Initial call: low=0, high=4, mid=2, arr[2]=6 matches target 6, so return 2.

2. Step 2: Return the index found

   Since arr[2] == 6, the function returns 2 immediately.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Index of 6 in array = 2 [OK]

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

Common Mistakes:

• Confusing index with value
• Not updating mid correctly
• Returning -1 when element is present

4. Find the error in the following binary search code snippet:

int binarySearch(int arr[], int low, int high, int x) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) low = mid;
        else high = mid - 1;
    }
    return -1;
}

medium

A. The update low = mid should be low = mid + 1.

B. The loop condition should be low < high.

C. The mid calculation can cause overflow.

D. The function should return mid + 1 instead of mid.

Solution

1. Step 1: Analyze the update of low pointer

   When arr[mid] < x, low should move to mid + 1 to avoid infinite loop.

2. Step 2: Identify the infinite loop cause

   Setting low = mid keeps low same if mid equals low, causing infinite loop.

3. Final Answer:

   The update low = mid should be low = mid + 1. -> Option A

4. Quick Check:

   Increment low past mid to avoid infinite loop [OK]

Hint: Increment low by 1 after mid when moving right [OK]

Common Mistakes:

• Not incrementing low causing infinite loop
• Using wrong loop condition
• Ignoring overflow in mid calculation

5. You have a sorted array with duplicate elements: {1, 2, 2, 2, 3, 4}. How can you modify binary search to find the first occurrence of 2?

hard

A. Return immediately when 2 is found.

B. Keep searching left half even after finding 2 to find first occurrence.

C. Search right half after finding 2 to find last occurrence.

D. Use linear search instead of binary search.

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 arr[mid] == target, continue searching left half to find earlier occurrence.

3. Step 3: Stop when mid is first or left element is different

   Return mid if it is first element or previous element is different.

4. Final Answer:

   Keep searching left half even after finding 2 to find first occurrence. -> Option B

5. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: After match, move left to find first duplicate [OK]

Common Mistakes:

• Returning first found index without checking left
• Searching right half after finding target
• Using linear search unnecessarily