Binary Search Iterative Approach in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search for Existing Element

What is the output of the following JavaScript code that performs an iterative binary search for the number 7 in a sorted array?

DSA Javascript

function binarySearch(arr, target) {
  let left = 0;
  let 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;
}

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

A -1

B 3

C 2

D 4

💡 Hint

Remember that array indices start at 0 and the array is sorted.

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

❓ Predict Output

intermediate

Output of Binary Search for Non-Existing Element

What is the output of the following JavaScript code that performs an iterative binary search for the number 7 in a sorted array?

DSA Javascript

function binarySearch(arr, target) {
  let left = 0;
  let 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;
}

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

A 0

B 3

C 2

D -1

💡 Hint

If the target is not found, the function returns -1.

The number 7 is not in the array [2, 4, 6, 8, 10], so the function returns -1.

🧠 Conceptual

advanced

Why Use Iterative Binary Search Instead of Recursive?

Which of the following is the main advantage of using an iterative binary search over a recursive binary search?

A Iterative binary search always runs faster than recursive binary search in all cases.

B Iterative binary search is easier to write and understand than recursive binary search.

C Iterative binary search uses less memory because it avoids the overhead of recursive calls.

D Iterative binary search can handle unsorted arrays without sorting them first.

💡 Hint

Think about how function calls use memory.

Recursive calls add overhead to the call stack, which uses more memory. Iterative binary search uses a loop and constant memory.

🔧 Debug

advanced

Identify the Bug in Binary Search Implementation

What is the output of the following JavaScript code when searching for 5 in the array?

DSA Javascript

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

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

A Returns 2 (correct index)

B Returns -1 (target not found)

C SyntaxError: Unexpected token

D TypeError: Cannot read property 'undefined' of undefined

💡 Hint

Check the initial value of the right pointer and array indexing.

The code returns 2 (correct index) because the target is found at mid=2 on the first iteration. However, right = arr.length is a bug: it risks out-of-bounds access to arr[arr.length] (undefined in JS).

🚀 Application

expert

Number of Iterations in Binary Search

Given a sorted array of length 31, what is the maximum number of iterations the iterative binary search algorithm will perform to find a target or conclude it is not present?

A 5

B 4

C 6

D 31

💡 Hint

Binary search halves the search space each iteration. Think about powers of 2.

Binary search reduces the search space by half each iteration. For 31 elements, maximum iterations = ceil(log2(31)) = 5.

Practice

1. What is the main purpose of the binary search iterative approach in a sorted array?

easy

A. To reverse the array elements

B. To find the position of a target value efficiently by repeatedly dividing the search interval in half

C. To sort the array elements in ascending order

D. To find the maximum value in the array

Solution

1. Step 1: Understand binary search goal

   Binary search aims to find a target value's position quickly in a sorted array by dividing the search space repeatedly.

2. Step 2: Identify the iterative approach

   The iterative method uses a loop to narrow down the search range until the target is found or the range is empty.

3. Final Answer:

   To find the position of a target value efficiently by repeatedly dividing the search interval in half -> Option B

4. Quick Check:

   Binary search = efficient position search [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Confusing binary search with sorting algorithms
• Thinking it works on unsorted arrays
• Assuming it finds maximum or minimum values

2. Which of the following is the correct way to initialize the mid index in an iterative binary search in JavaScript?

easy

A. const mid = Math.ceil((start + end) / 2);

B. const mid = (start + end) / 2;

C. const mid = Math.floor((start + end) / 2);

D. const mid = start + end;

Solution

1. Step 1: Understand index calculation

   Mid index must be an integer index, so we use Math.floor to round down the average of start and end.

2. Step 2: Check options for correct syntax

   const mid = Math.floor((start + end) / 2); uses Math.floor((start + end) / 2), which correctly calculates the middle index as an integer.

3. Final Answer:

   const mid = Math.floor((start + end) / 2); -> Option C

4. Quick Check:

   Mid index = Math.floor average [OK]

Hint: Use Math.floor to get integer mid index [OK]

Common Mistakes:

• Using division without floor, resulting in float index
• Using Math.ceil which can cause out-of-range index
• Adding start and end without division

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

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

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

medium

A. 2

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace the binary search steps

   Array is [2,4,6,8,10], target is 6. Initial start=0, end=4, mid=2. arr[2] = 6 matches target.

2. Step 2: Return index when found

   Since arr[mid] equals target, function returns mid = 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value first for quick match [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in start/end updates
• Returning value instead of index

4. Identify the bug in the following iterative binary search code snippet:

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

medium

A. The loop condition should be start <= end instead of start < end

B. The mid calculation should use Math.ceil instead of Math.floor

C. The function should return arr[mid] instead of mid

D. The start should be initialized to 1 instead of 0

Solution

1. Step 1: Analyze loop condition impact

   The loop uses start < end, which misses the case when start equals end, possibly skipping the last element check.

2. Step 2: Correct loop condition for full search

   Changing to start <= end ensures the loop checks all elements including when start equals end.

3. Final Answer:

   The loop condition should be start <= end instead of start < end -> Option A

4. Quick Check:

   Loop condition must include equality [OK]

Hint: Use <= to include last element in search [OK]

Common Mistakes:

• Using < excludes last element check
• Changing mid calculation unnecessarily
• Returning value instead of index

5. Given a sorted array with possible duplicate values, how can you modify the iterative binary search to find the first occurrence of a target value?

function binarySearchFirst(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  let result = -1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) {
      result = mid;
      end = mid - 1; // Continue searching left
    } else if (arr[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return result;
}

hard

A. Search right side by moving start to mid + 1 when target is found

B. Return immediately when target is found at mid

C. Change mid calculation to use Math.ceil instead of Math.floor

D. Keep track of found index and continue searching left by moving end to mid - 1

Solution

1. Step 1: Understand duplicate handling

   To find first occurrence, we must not stop at first match but continue searching left side.

2. Step 2: Use result variable and adjust end pointer

   Store current match index in result, then move end to mid - 1 to search left side for earlier occurrence.

3. Final Answer:

   Keep track of found index and continue searching left by moving end to mid - 1 -> Option D

4. Quick Check:

   Track index + search left for first occurrence [OK]

Hint: On match, move left to find first occurrence [OK]

Common Mistakes:

• Stopping search immediately on first match
• Searching right side instead of left
• Ignoring duplicates in binary search