Binary Search as Divide and Conquer in DSA C

Mental Model

Binary search splits a sorted list into halves to quickly find a target value by ignoring half the list each time.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is in the left or right half, and repeating this until you find it.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Indices:    0      1      2      3      4       5       6
Search range: low=0 ↑                 mid=3 ↑                 high=6 ↑

Dry Run Walkthrough

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

Goal: Find the index of the target value 7 in the sorted array using binary search.

Step 1: Calculate mid index as (0 + 6) / 2 = 3, check value at mid (7).

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> null

Why: We start by checking the middle element to decide which half to search next.

Step 2: Compare mid value (7) with target (7), they are equal.

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> null

Why: Found the target at mid index, so we stop searching.

Result:

Final state: [1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> null
Answer: Target 7 found at index 3

Annotated Code

DSA C

#include <stdio.h>

int binary_search(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2; // find middle index
        if (arr[mid] == target) {
            return mid; // target found
        } 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() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = binary_search(arr, 0, size - 1, target);
    if (result != -1) {
        printf("Target %d found at index %d\n", target, result);
    } else {
        printf("Target %d not found in array\n", target);
    }
    return 0;
}

int mid = low + (high - low) / 2; // find middle index

Calculate middle index to split the search range.

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

Check if middle element is the target; if yes, return index.

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

If middle element is less than target, search right half.

else { high = mid - 1; }

If middle element is greater than target, search left half.

Output

Target 7 found at index 3

Complexity Analysis

Time: O(log n) because each step halves the search range, quickly narrowing down the target.

Space: O(1) because the search uses only a few variables and no extra space proportional to input size.

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by skipping half the elements each step.

Edge Cases

Empty array

Function returns -1 immediately because low > high.

DSA C

while (low <= high)

Target smaller than all elements

Search narrows to left side and returns -1 when no match found.

DSA C

while (low <= high)

Target larger than all elements

Search narrows to right side and returns -1 when no match found.

DSA C

while (low <= high)

When to Use This Pattern

When you need to find an element quickly in a sorted list, use binary search because it divides the problem into smaller parts 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 loops.
Fix: Ensure low = mid + 1 or high = mid - 1 to shrink search range properly.

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 to find an element efficiently.

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 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