Why Binary Search and What Sorted Order Gives You in DSA C++ - Performance Analysis

Time Complexity: Why Binary Search and What Sorted Order Gives You

O(log n)

Understanding Time Complexity

We want to understand why binary search is faster than simple search methods.

How does having a sorted list help us find items quickly?

Scenario Under Consideration

Analyze the time complexity of the following binary search code.

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

This code searches for a target value in a sorted array by repeatedly dividing the search range in half.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the middle element of the current search range.
• How many times: The search range halves each time, so this happens about log₂(n) times.

How Execution Grows With Input

Each step cuts the search area in half, so the number of steps grows slowly as the list gets bigger.

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

Pattern observation: Doubling the input size adds only one more check.

Final Time Complexity

Time Complexity: O(log n)

This means the number of steps grows very slowly even if the list becomes very large.

Common Mistake

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

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

Interview Connect

Understanding binary search shows you how sorting helps speed up searching, a key skill in many coding problems.

Self-Check

"What if the array was not sorted? How would that change the time complexity of searching for a target?"