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

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

O(log n)

Understanding Time Complexity

We want to see how fast searching works when the list is sorted.

How does sorting help us find items quicker?

Scenario Under Consideration

Analyze the time complexity of the following binary search code.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
    

This code looks for a target number in a sorted array by repeatedly cutting the search area in half.

Identify Repeating Operations

Look at what repeats as the code runs.

• Primary operation: Checking the middle element and adjusting the search range.
• How many times: The search range halves each time, so the loop runs about log base 2 of n times.

How Execution Grows With Input

As the list gets bigger, the number of steps grows slowly.

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 slowly as the list gets bigger, making search very fast.

Common Mistake

[X] Wrong: "Binary search works on any list, sorted or not."

[OK] Correct: Without sorting, cutting the list in half doesn't guarantee the target is in one half, so binary search won't work correctly.

Interview Connect

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

Self-Check

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