Binary Search as Divide and Conquer in DSA C++

Mental Model

Binary search splits a sorted list into halves repeatedly to find a target quickly.

Analogy: Like guessing a number between 1 and 100 by asking if it's higher or lower than the middle number, cutting the search space in half each time.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:     [0, 1, 2, 3, 4,  5,  6]
Search range: ↑--------------------↑
Middle:          ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], target: 9

Goal: Find the index of target 9 in the array using binary search

Step 1: Calculate middle index between low=0 and high=6, mid=3; compare array[mid]=7 with target=9

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5   6
low=0 ↑           mid=3 ↑           high=6 ↑

Why: We check middle to decide which half to search next

Step 2: Since 7 < 9, move low to mid+1=4 to search right half

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5   6
          low=4 ↑           high=6 ↑

Why: Target must be in right half because 9 > 7

Step 3: Calculate middle index between low=4 and high=6, mid=5; compare array[mid]=11 with target=9

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5   6
              low=4 ↑ mid=5 ↑ high=6 ↑

Why: Check middle of new search range to narrow down

Step 4: Since 11 > 9, move high to mid-1=4 to search left half

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5   6
              low=4 ↑       high=4 ↑

Why: Target must be in left half because 9 < 11

Step 5: Calculate middle index between low=4 and high=4, mid=4; compare array[mid]=9 with target=9

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5   6
              low=4 ↑ mid=4 ↑ high=4 ↑

Why: Check the last remaining element

Step 6: Found target at index 4; return index 4

[1, 3, 5, 7, 9, 11, 13]
Indices: 0  1  2  3  4  5   6
              ↑ target found

Why: Target matches middle element

Result:

Final state: target 9 found at index 4

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& arr, int target) {
    int low = 0;
    int high = (int)arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // avoid overflow
        if (arr[mid] == target) {
            return mid; // found target
        } else if (arr[mid] < target) {
            low = mid + 1; // search right half
        } else {
            high = mid - 1; // search left half
        }
    }
    return -1; // target not found
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 9;
    int index = binarySearch(arr, target);
    if (index != -1) {
        cout << "Target found at index: " << index << "\n";
    } else {
        cout << "Target not found\n";
    }
    return 0;
}

int mid = low + (high - low) / 2; // avoid overflow

Calculate middle index to split search range

if (arr[mid] == target) { return mid; }

Check if middle element is target

else if (arr[mid] < target) { low = mid + 1; }

If middle less than target, search right half

else { high = mid - 1; }

If middle greater than target, search left half

Output

Target found at index: 4

Complexity Analysis

Time: O(log n) because each step halves the search space until target is found or range is empty

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by dividing the problem repeatedly

Edge Cases

Empty array

Returns -1 immediately as low > high

DSA C++

while (low <= high)

Target smaller than all elements

Search narrows and returns -1 after range is empty

DSA C++

while (low <= high)

Target larger than all elements

Search narrows and returns -1 after range is empty

DSA C++

while (low <= high)

Single element array with target present

Returns index 0 immediately

DSA C++

if (arr[mid] == target) { return mid; }

Single element array with target absent

Returns -1 after one check

DSA C++

while (low <= high)

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it divides the search space in half each step.

Common Mistakes

Mistake: Calculating mid as (low + high) / 2 can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly causing infinite loop
Fix: Ensure low = mid + 1 or high = mid - 1 to shrink search range

Mistake: Using binary search on unsorted array
Fix: Sort the array first or use linear search

Summary

Binary search finds a target in a sorted array by repeatedly dividing the search range in half.

Use it when you have a sorted list and want fast search.

The key insight is cutting the search space in half each step to quickly zero in on the target.

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