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.