Binary Search as Divide and Conquer in DSA Javascript - Execution Trace

Concept Flow - Binary Search as Divide and Conquer

Start with sorted array and target

↓

Calculate middle index

↓

Compare middle element with target

↓

Equal?

↓

Found

↓

Search right half

↓

Repeat until found or empty

Binary search splits the sorted array in half each time, comparing the middle element to the target, then searching the left or right half accordingly until the target is found or the search space is empty.

Execution Sample

DSA Javascript

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    let 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 searches for a target number in a sorted array by repeatedly dividing the search range in half.

Execution Table

Step	Operation	Left Index	Right Index	Middle Index	Middle Value	Comparison	Action	Visual State
1	Initialize	0	6	-	-	-	Start search in full array	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 vs 9	7 < 9, move left to mid+1	[1, 3, 5, 7, 9, 11, 13]
3	Update left	4	6	-	-	-	Search right half	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	6	5	11	11 vs 9	11 > 9, move right to mid-1	[1, 3, 5, 7, 9, 11, 13]
5	Update right	4	4	-	-	-	Search left half	[1, 3, 5, 7, 9, 11, 13]
6	Calculate mid	4	4	4	9	9 vs 9	Found target at index 4	[1, 3, 5, 7, 9, 11, 13]
7	Return	-	-	-	-	-	Return index 4	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	4	4	4	4	4
right	6	6	6	6	4	4	4
mid	-	3	-	5	-	4	4
middleValue	-	7	-	11	-	9	9

Key Moments - 3 Insights

Why do we update 'left' to mid + 1 when middle value is less than target?

Because the middle value is smaller than the target, the target must be in the right half, so we move 'left' to mid + 1 to search only the right half. See execution_table step 3.

Why do we update 'right' to mid - 1 when middle value is greater than target?

Because the middle value is larger than the target, the target must be in the left half, so we move 'right' to mid - 1 to search only the left half. See execution_table step 5.

Why does the loop stop when left > right?

When 'left' passes 'right', it means the search space is empty and the target is not found. The loop ends to avoid infinite searching.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'mid' at step 4?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'Middle Index' column in execution_table row for step 4.

At which step does the search space reduce to a single element?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at 'Left Index' and 'Right Index' columns to find when they are equal.

If the target was 12 instead of 9, what would happen at step 5?

A Right would update to mid - 1

B Left would update to mid + 1

C Target found at mid

D Loop ends immediately

💡 Hint

Compare how the code updates 'left' or 'right' based on middle value vs target in execution_table steps 3 and 5.

Concept Snapshot

Binary Search divides a sorted array into halves to find a target.
Calculate middle index: mid = (left + right) // 2.
Compare middle value with target.
If equal, return mid.
If target > middle, search right half (left = mid + 1).
If target < middle, search left half (right = mid - 1).
Repeat until found or search space empty.

Full Transcript

Binary search is a method to find a target value in a sorted array by repeatedly dividing the search range in half. We start with the full array, calculate the middle index, and compare the middle element with the target. If they match, we return the index. If the target is greater, we search the right half by moving the left pointer to mid + 1. If the target is smaller, we search the left half by moving the right pointer to mid - 1. This process repeats until the target is found or the search space is empty, meaning the target is not in the array.

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