Why Binary Search and What Sorted Order Gives You in DSA Javascript - Why This Pattern

Mental Model

Binary search quickly finds a value by repeatedly cutting the search area in half, but it only works if the list is sorted.

Analogy: Imagine looking for a word in a dictionary. You don't check every page; you open near the middle, decide which half to search next, and keep narrowing down until you find the word.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Indices:       0      1      2      3      4       5       6

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], search for 9

Goal: Find the position of 9 quickly using binary search

Step 1: Check middle element at index 3 (value 7)

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> null

Why: We start in the middle to decide which half to search next

Step 2: Since 9 > 7, search right half from index 4 to 6

[9] -> [11] -> [13] -> null (search area)

Why: 9 must be in the right half because the array is sorted

Step 3: Check middle element of right half at index 5 (value 11)

[9] -> [11↑] -> [13] -> null

Why: Check middle of new search area to narrow down further

Step 4: Since 9 < 11, search left half of right half, index 4 only

[9↑] -> null

Why: 9 must be before 11 in the sorted array

Step 5: Check element at index 4 (value 9), found target

[9↑] -> null

Why: We found the value 9 at index 4

Result:

[1] -> [3] -> [5] -> [7] -> [9↑] -> [11] -> [13] -> null
Answer: Found 9 at index 4

Annotated Code

DSA Javascript

class BinarySearch {
  static search(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2); // find middle index
      if (arr[mid] === target) {
        return mid; // found target
      } else if (arr[mid] < target) {
        left = mid + 1; // search right half
      } else {
        right = mid - 1; // search left half
      }
    }
    return -1; // target not found
  }
}

const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 9;
const index = BinarySearch.search(arr, target);
if (index !== -1) {
  console.log(`Found ${target} at index ${index}`);
} else {
  console.log(`${target} not found in array`);
}

const mid = Math.floor((left + right) / 2); // find middle index

calculate middle index to split search area

if (arr[mid] === target) { return mid; }

check if middle element is the target

else if (arr[mid] < target) { left = mid + 1; }

move left pointer to right half if target is greater

else { right = mid - 1; }

move right pointer to left half if target is smaller

Output

Found 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Linear search takes O(n) by checking each element one by one, which is slower for large sorted arrays

Edge Cases

empty array

returns -1 immediately because left > right

DSA Javascript

while (left <= right) {

target smaller than all elements

search narrows and returns -1 after checking left half

DSA Javascript

right = mid - 1;

target larger than all elements

search narrows and returns -1 after checking right half

DSA Javascript

left = mid + 1;

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it cuts the search area in half each time, making it very fast.

Common Mistakes

Mistake: Trying binary search on an unsorted array
Fix: Always sort the array first or use a different search method

Summary

Binary search finds a target value quickly by repeatedly dividing a sorted list in half.

Use binary search when you have a sorted list and want fast search times.

The key insight is that sorted order lets you ignore half the list each step, making search much faster.