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

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

O(log n)

Understanding Time Complexity

We want to understand why searching in a sorted list is faster with binary search.

How does sorting help us find items quickly?

Scenario Under Consideration

Analyze the time complexity of this binary search code.

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        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 number in a sorted list by repeatedly dividing the search area in half.

Identify Repeating Operations

Look at what repeats in the code.

• Primary operation: Checking the middle element of the current search range.
• How many times: The search range halves each time, repeating until the target is found or range is empty.

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 (mid checks)
10	About 4
100	About 7
1000	About 10

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 search very fast even for large lists.

Common Mistake

[X] Wrong: "Binary search is always faster than linear search no matter what."

[OK] Correct: Binary search only works on sorted lists; if the list is unsorted, linear search is needed first or sorting must be done, which takes extra time.

Interview Connect

Understanding binary search shows you how sorting helps speed up searching, a key skill for efficient coding and problem solving.

Self-Check

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