Binary Search as Divide and Conquer in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index in binary search.

DSA Javascript

const mid = Math.floor((low + [1]) / 2);

Drag options to blanks, or click blank then click option'

Ahigh

Bmid

Clow

Darr.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using mid before it is defined.

Using arr.length instead of high.

The middle index is calculated by averaging low and high indices.

2fill in blank

medium

Complete the code to check if the middle element is the target.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Ahigh

Bmid

Clow

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing arr[mid] to mid index.

Comparing arr[mid] to low or high indices.

We compare the middle element with the target value.

3fill in blank

hard

Fix the error in updating the low index when target is greater than middle element.

DSA Javascript

if (arr[mid] < target) { low = [1]; }

Drag options to blanks, or click blank then click option'

Ahigh - 1

Bmid

Cmid + 1

Dlow + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting low to mid causes infinite loop.

Setting low to low + 1 misses the correct position.

We move low to mid + 1 to search the right half excluding mid.

4fill in blank

hard

Fill both blanks to update high index when target is less than middle element.

DSA Javascript

if (arr[mid] > target) { high = [1]; } else { low = [2]; }

Drag options to blanks, or click blank then click option'

Amid - 1

Bmid + 1

Chigh - 1

Dlow + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using high - 1 instead of mid - 1.

Using low + 1 incorrectly.

When target is less, high moves to mid - 1; else low moves to mid + 1.

5fill in blank

hard

Fill all three blanks to complete the binary search function.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Ahigh

Btarget

Cmid + 1

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables in mid calculation.

Comparing arr[mid] to wrong variable.

Incorrectly updating low index.

Mid is average of low and high; compare arr[mid] to target; update low to mid + 1 if target is greater.

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