Binary Search as Divide and Conquer in DSA Javascript

Mental Model

Binary search splits a sorted list into halves to quickly find a target value by ignoring half the list each time.

Analogy: Like looking for a word in a dictionary by opening it in the middle and deciding if the word is before or after that page, then repeating on the chosen half.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:     [0, 1, 2, 3, 4,  5,  6]
Start -> 0, End -> 6, Mid -> 3 (value 7)

Dry Run Walkthrough

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

Goal: Find the index of the target value 9 in the array using binary search

Step 1: Calculate mid index: (0 + 6) // 2 = 3, check value at mid (7)

[1, 3, 5, [7], 9, 11, 13]

Why: We start by checking the middle element to decide which half to search next

Step 2: Target 9 is greater than mid value 7, so move start to mid + 1 = 4

start=4, end=6, array: [1, 3, 5, 7, [9], 11, 13]

Why: Since target is bigger, we ignore left half including mid and search right half

Step 3: Calculate new mid: (4 + 6) // 2 = 5, check value at mid (11)

[1, 3, 5, 7, 9, [11], 13]

Why: Check middle of the new search range to narrow down further

Step 4: Target 9 is less than mid value 11, so move end to mid - 1 = 4

start=4, end=4, array: [1, 3, 5, 7, [9], 11, 13]

Why: Since target is smaller, ignore right half including mid and search left half

Step 5: Calculate new mid: (4 + 4) // 2 = 4, check value at mid (9)

[1, 3, 5, 7, [9], 11, 13]

Why: Check the only remaining element in the search range

Step 6: Found target 9 at index 4, return index

[1, 3, 5, 7, [9], 11, 13]

Why: Target matches mid value, search ends successfully

Result:

Final state: [1, 3, 5, 7, [9], 11, 13]
Answer: index 4

Annotated Code

DSA Javascript

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

// Driver code
const array = [1, 3, 5, 7, 9, 11, 13];
const target = 9;
const result = BinarySearch.search(array, target);
if (result !== -1) {
  console.log(`Target found at index ${result}`);
} else {
  console.log('Target not found');
}

const mid = Math.floor((start + end) / 2); // find middle index

Calculate middle index to split search range

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

Check if middle element is the target

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

If target is greater, move start to right half

else { end = mid - 1; }

If target is smaller, move end to left half

Output

Target found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space, quickly narrowing down to the target

Space: O(1) because it uses only a few variables and no extra space proportional to input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by skipping half the elements each step

Edge Cases

Empty array

Returns -1 immediately since start > end

DSA Javascript

while (start <= end) {

Target not in array

Search narrows until start > end and returns -1

DSA Javascript

return -1; // target not found

Single element array with target present

Returns index 0 immediately if element matches target

DSA Javascript

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

When to Use This Pattern

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

Common Mistakes

Mistake: Calculating mid as (start + end) / 2 without floor, causing float index
Fix: Use Math.floor to get an integer index

Mistake: Not updating start or end correctly, causing infinite loop
Fix: Ensure start = mid + 1 or end = mid - 1 to shrink search space

Mistake: Using binary search on unsorted array
Fix: Sort the array first or use linear search

Summary

Binary search finds a target in a sorted array by repeatedly dividing the search range in half.

Use it when you have a sorted list and want fast search performance.

The key insight is cutting the search space in half each step to quickly zero in on the target.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It sorts the array before searching for the target.

B. It checks every element one by one until it finds the target.

C. It repeatedly divides the search interval in half to find the target value.

D. It uses random guesses to find the target quickly.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the array into two halves and decides which half to search next.

2. Step 2: Identify the repeated halving process

   It keeps dividing the search space by half until the target is found or no elements remain.

3. Final Answer:

   It repeatedly divides the search interval in half to find the target value. -> Option C

4. Quick Check:

   Divide and conquer = halve search space [OK]

Hint: Binary search halves the array each step to find the target [OK]

Common Mistakes:

• Thinking binary search checks every element
• Confusing binary search with linear search
• Assuming binary search sorts the array

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

easy

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

B. const mid = low + high / 2;

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

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

Solution

1. Step 1: Understand middle index calculation

   The middle index should be an integer, so we use Math.floor to round down.

2. Step 2: Check each option

   const mid = (low + high) / 2; returns a float, const mid = Math.floor((low + high) / 2); correctly floors the average, const mid = Math.ceil((low + high) / 2); rounds up which can cause errors, const mid = low + high / 2; has wrong operator precedence.

3. Final Answer:

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

4. Quick Check:

   Use Math.floor to get integer mid [OK]

Hint: Use Math.floor((low + high) / 2) for middle index [OK]

Common Mistakes:

• Not flooring the middle index causing float errors
• Using wrong operator precedence without parentheses
• Using Math.ceil which can skip elements

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

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const 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;
}

const nums = [2, 4, 6, 8, 10];
console.log(binarySearch(nums, 6));

medium

A. 2

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace the binary search for target 6

   Initial low=0, high=4, mid=2 (element 6). arr[mid] equals target, so return 2.

2. Step 2: Confirm returned index

   The function returns index 2 where 6 is found.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value matches target to return index [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Returning value instead of index

4. Identify the bug in this binary search code snippet and choose the correct fix:

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length;
  while (low <= high) {
    const 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. Change while condition to low < high

B. Change high initialization to arr.length - 1

C. Use Math.ceil instead of Math.floor for mid

D. Return arr[mid] instead of mid

Solution

1. Step 1: Check high initialization

   High should be last index, which is arr.length - 1, not arr.length (out of bounds).

2. Step 2: Confirm fix

   Changing high to arr.length - 1 prevents accessing undefined elements and infinite loop.

3. Final Answer:

   Change high initialization to arr.length - 1 -> Option B

4. Quick Check:

   High = arr.length - 1 fixes index error [OK]

Hint: Set high to last index: arr.length - 1 [OK]

Common Mistakes:

• Setting high to arr.length causing out-of-bounds
• Changing while condition incorrectly
• Returning value instead of index

5. You have a sorted array arr = [1, 3, 3, 5, 7, 7, 7, 9]. Using binary search as divide and conquer, which index will be returned when searching for 7 with the standard binary search implementation below?

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const 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;
}

Choose the correct index returned and explain why.

hard

A. 5 (middle occurrence of 7)

B. 6 (last occurrence of 7)

C. 4 (first occurrence of 7)

D. -1 (not found)

Solution

1. Step 1: Trace binary search on duplicates

   Initial low=0, high=7, mid=3 (arr[3]=5 < 7), so low=4. Next mid=5 (arr[5]=7), matches target, returns 5 immediately.

2. Step 2: Understand standard binary search behavior

   Standard binary search returns the first found match, not necessarily first or last occurrence.

3. Final Answer:

   5 (middle occurrence of 7) -> Option A

4. Quick Check:

   Standard binary search returns any matching index [OK]

Hint: Standard binary search returns any matching index, not first or last [OK]

Common Mistakes:

• Assuming it always returns first or last occurrence
• Ignoring duplicates in array
• Expecting -1 when target exists