Binary Search as Divide and Conquer in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search Call

What is the output of the following JavaScript code that uses recursive binary search to find the index of number 7 in the array?

DSA Javascript

function binarySearch(arr, target, left, right) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right);
  else return binarySearch(arr, target, left, mid - 1);
}

const array = [1, 3, 5, 7, 9, 11];
const index = binarySearch(array, 7, 0, array.length - 1);
console.log(index);

A 3

B 2

C -1

D 4

💡 Hint

Remember that array indices start at 0 and binary search returns the index where the target is found.

The number 7 is at index 3 in the array [1, 3, 5, 7, 9, 11]. The binary search correctly finds and returns this index.

🧠 Conceptual

intermediate

Divide and Conquer Principle in Binary Search

Which statement best describes how binary search uses the divide and conquer approach?

A It splits the array into two halves and recursively searches only the half that may contain the target.

B It divides the array into multiple parts and searches all parts in parallel.

C It searches both halves of the array simultaneously to find the target faster.

D It searches the entire array linearly but divides the target value by two each step.

💡 Hint

Think about how binary search reduces the search space at each step.

Binary search divides the array into two halves and only continues searching in the half where the target could be, ignoring the other half. This is the core of divide and conquer.

❓ Predict Output

advanced

Output of Iterative Binary Search with Missing Element

What is the output of this iterative binary search code when searching for 8 in the array?

DSA Javascript

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

const array = [2, 4, 6, 10, 12];
const result = binarySearchIterative(array, 8);
console.log(result);

A 0

B 2

C 3

D -1

💡 Hint

If the target is not found, binary search returns -1.

The number 8 is not in the array. The binary search completes without finding it and returns -1.

🔧 Debug

advanced

Identify the Error in Binary Search Implementation

What error will this recursive binary search code produce when searching for 9 in the array?

DSA Javascript

function binarySearch(arr, target, left, right) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right);
  else return binarySearch(arr, target, left, mid - 1);
}

const array = [1, 3, 5, 7, 9];
const index = binarySearch(array, 9, 0, array.length - 1);
console.log(index);

A Returns -1 even though 9 is in the array

B Returns 4 correctly

C Causes infinite recursion and stack overflow

D Throws a TypeError

💡 Hint

Check the base case condition carefully.

The base case uses 'left > right' which correctly allows searching when left equals right, so the function finds the target at index 4 and returns it.

🧠 Conceptual

expert

Time Complexity of Binary Search

What is the time complexity of binary search and why?

A O(1) because it finds the element immediately

B O(n log n) because it divides and sorts the array

C O(log n) because the search space halves with each step

D O(n) because it checks each element once

💡 Hint

Think about how many times you can divide the array in half before it becomes empty.

Binary search cuts the search space in half each time, so the number of steps grows logarithmically with the size of the array, which is O(log n).

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