Binary Search Iterative Approach in DSA Go - Time & Space Complexity

Time Complexity: Binary Search Iterative Approach

O(log n)

Understanding Time Complexity

We want to understand how the time taken by binary search changes as the list size grows.

Specifically, how many steps does it take to find a number in a sorted list?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        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
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop that halves the search range each time.
• How many times: The loop runs until the search range is empty, roughly halving the size each time.

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 input size adds only one extra step.

Final Time Complexity

Time Complexity: O(log n)

This means the steps needed grow slowly, increasing by one step each time the list size doubles.

Common Mistake

[X] Wrong: "Binary search checks every element one by one, so it is O(n)."

[OK] Correct: Binary search does not check every element; it cuts the search area in half each time, so it takes far fewer steps than checking all elements.

Interview Connect

Knowing how binary search scales helps you explain efficient searching in sorted data, a common skill interviewers look for.

Self-Check

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