Binary Search as Divide and Conquer in DSA C - Time & Space Complexity

Time Complexity: Binary Search as Divide and Conquer

O(log n)

Understanding Time Complexity

We want to understand how fast binary search finds an item in a sorted list.

How does the number of steps change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code searches for a target number by repeatedly dividing the list in half.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the middle element and deciding which half to search next.
• How many times: The search space halves each time, so this happens about log₂(n) times.

How Execution Grows With Input

Each step cuts the list size in half, so the number of steps grows slowly as the list grows.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the list size adds only one extra step.

Final Time Complexity

Time Complexity: O(log n)

This means the number of steps grows slowly, making binary search very efficient for large lists.

Common Mistake

[X] Wrong: "Binary search checks every element like a simple search."

[OK] Correct: Binary search skips half the list each time, so it does far fewer checks than searching one by one.

Interview Connect

Understanding binary search time helps you explain efficient searching clearly and confidently in interviews.

Self-Check

"What if the list was not sorted? How would the time complexity of searching change?"