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.

Practice

1. Why is binary search only applicable on a sorted list?

easy

A. Because it can search any list regardless of order

B. Because it relies on comparing the middle element to decide which half to search next

C. Because it checks every element one by one

D. Because it sorts the list before searching

Solution

1. Step 1: Understand binary search logic

   Binary search works by comparing the middle element to the target and deciding which half to continue searching.

2. Step 2: Importance of sorted order

   This logic only works if the list is sorted, so we know which half contains the target based on comparison.

3. Final Answer:

   Because it relies on comparing the middle element to decide which half to search next -> Option B

4. Quick Check:

   Binary search needs sorted list = Because it relies on comparing the middle element to decide which half to search next [OK]

Hint: Binary search splits sorted list by middle comparison [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Confusing binary search with linear search
• Assuming binary search sorts the list automatically

2. Which of the following is the correct syntax to find the middle index in a binary search on array arr between indices low and high in JavaScript?

easy

A. const mid = Math.floor((low + high) / 2);

B. const mid = (low + high) / 2;

C. const mid = Math.ceil((low + high) / 2);

D. const mid = low + high;

Solution

1. Step 1: Calculate middle index correctly

   The middle index should be the floor of the average of low and high to get an integer index.

2. Step 2: Check each option

   const mid = Math.floor((low + high) / 2); uses Math.floor which correctly rounds down. const mid = (low + high) / 2; returns a float, const mid = Math.ceil((low + high) / 2); rounds up which can cause errors, const mid = low + high; sums indices without division.

3. Final Answer:

   const mid = Math.floor((low + high) / 2); -> Option A

4. Quick Check:

   Use Math.floor for middle index [OK]

Hint: Use Math.floor to get integer middle index [OK]

Common Mistakes:

• Not using Math.floor causing float index
• Using Math.ceil causing off-by-one errors
• Adding indices without dividing

3. What will be the output of the following JavaScript code?

const arr = [2, 4, 6, 8, 10];
function binarySearch(array, target) {
  let low = 0, high = array.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (array[mid] === target) return mid;
    else if (array[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}
console.log(binarySearch(arr, 8));

medium

A. 3

B. 2

C. -1

D. 4

Solution

1. Step 1: Trace binary search steps for target 8

   Initial low=0, high=4, mid=2 (value 6). Since 6 < 8, low = mid+1 = 3.

2. Step 2: Next iteration mid=3 (value 8), matches target, return 3

   The function returns index 3 where 8 is found.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Index of 8 in array = 3 [OK]

Hint: Trace mid updates to find target index [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Returning -1 incorrectly

4. The following binary search code has a bug. What is the error?

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

medium

A. The loop condition should be low < high, not low <= high

B. low should start at 1, not 0

C. mid calculation should use Math.ceil instead of Math.floor

D. high should be initialized to arr.length - 1, not arr.length

Solution

1. Step 1: Check initialization of high

   Array indices go from 0 to length-1, so high must be arr.length - 1 to avoid out-of-bounds.

2. Step 2: Consequences of wrong high value

   Setting high = arr.length causes mid to sometimes be arr.length, which is invalid index and causes errors.

3. Final Answer:

   high should be initialized to arr.length - 1, not arr.length -> Option D

4. Quick Check:

   High index = length - 1 [OK]

Hint: High index must be last valid array index [OK]

Common Mistakes:

• Setting high to arr.length causing index errors
• Changing low start incorrectly
• Changing loop condition wrongly

5. You have a sorted array arr = [1, 3, 3, 5, 7, 7, 7, 9]. You want to find the first occurrence of the number 7 using binary search. Which modification helps achieve this?

hard

A. Use linear search instead of binary search

B. Return mid immediately when arr[mid] equals target

C. When arr[mid] equals target, continue searching left half to find first occurrence

D. Search right half when arr[mid] equals target

Solution

1. Step 1: Understand duplicate elements in sorted array

   Binary search normally returns any matching index, but to find first occurrence, we must check if earlier indices also have the target.

2. Step 2: Modify search to continue left when target found

   When arr[mid] equals target, update result but continue searching left half to find earlier occurrence.

3. Final Answer:

   When arr[mid] equals target, continue searching left half to find first occurrence -> Option C

4. Quick Check:

   Search left half on match for first occurrence [OK]

Hint: On match, search left half to find first occurrence [OK]

Common Mistakes:

• Returning immediately on first match
• Searching right half on match
• Using linear search unnecessarily