Binary Search as Divide and Conquer in DSA Javascript - Build from Scratch

Binary Search as Divide and Conquer

📖 Scenario: You have a sorted list of numbers representing book IDs in a library. You want to quickly find if a specific book ID is available.

🎯 Goal: Build a binary search function using divide and conquer to find a book ID in the sorted list.

📋 What You'll Learn

Create a sorted array called bookIDs with the exact values: [101, 203, 305, 407, 509, 611, 713]

Create a variable called targetID and set it to 407

Write a function called binarySearch that takes arr, target, start, and end as parameters and returns the index of target or -1 if not found

Use console.log to print the result of binarySearch(bookIDs, targetID, 0, bookIDs.length - 1)

💡 Why This Matters

🌍 Real World

Binary search is used in many apps and systems to quickly find data in sorted lists, like searching for a contact in a phone book or a product in an online store.

💼 Career

Understanding binary search is important for software developers and data analysts to write efficient search algorithms and optimize performance.

1

Create the sorted array of book IDs

Create a sorted array called bookIDs with these exact values: [101, 203, 305, 407, 509, 611, 713]

DSA Javascript

# Your code here

Hint

Use const to create the array with the exact numbers in order.

2

Set the target book ID to search

Create a variable called targetID and set it to 407

DSA Javascript

const bookIDs = [101, 203, 305, 407, 509, 611, 713];
# Your code here

Hint

Use const to create targetID with the value 407.

3

Write the binary search function

Write a function called binarySearch that takes parameters arr, target, start, and end. Use divide and conquer by finding the middle index, comparing arr[middle] with target, and recursively searching the left or right half. Return the index if found, or -1 if not found.

DSA Javascript

const bookIDs = [101, 203, 305, 407, 509, 611, 713];
const targetID = 407;

# Your code here

Hint

Use recursion to split the array and compare the middle element with the target.

4

Print the search result

Use console.log to print the result of calling binarySearch(bookIDs, targetID, 0, bookIDs.length - 1)

DSA Javascript

const bookIDs = [101, 203, 305, 407, 509, 611, 713];
const targetID = 407;

function binarySearch(arr, target, start, end) {
    if (start > end) {
        return -1;
    }
    const middle = Math.floor((start + end) / 2);
    if (arr[middle] === target) {
        return middle;
    } else if (arr[middle] > target) {
        return binarySearch(arr, target, start, middle - 1);
    } else {
        return binarySearch(arr, target, middle + 1, end);
    }
}

# Your code here

Hint

The index of 407 in bookIDs is 3. Use console.log to print it.

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