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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search for Existing Element

What is the output of the following TypeScript code that uses iterative binary search to find the index of the number 7 in the sorted array?

DSA Typescript

function binarySearch(arr: number[], target: number): number {
  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 arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(arr, 7));

A 4

B 3

C -1

D 2

💡 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 its index.

❓ Predict Output

intermediate

Output of Binary Search for Non-Existing Element

What will be the output of this TypeScript code when searching for the number 8 in the sorted array?

DSA Typescript

function binarySearch(arr: number[], target: number): number {
  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 arr = [2, 4, 6, 10, 12];
console.log(binarySearch(arr, 8));

A 0

B 2

C 3

D -1

💡 Hint

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

The number 8 is not in the array, so the binary search returns -1 to indicate it was not found.

🧠 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 uses less memory because it avoids the overhead of recursive calls.

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

C Iterative binary search always finds the target faster than recursive binary search.

D Iterative binary search can handle unsorted arrays better than recursive binary search.

💡 Hint

Think about how function calls use memory.

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

🔧 Debug

advanced

Identify the Bug in Binary Search Implementation

What is the bug in this iterative binary search code that causes it to fail for some inputs?

DSA Typescript

function binarySearch(arr: number[], target: number): number {
  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;
}

A The right boundary should be initialized to arr.length - 1, not arr.length.

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

C The loop condition should be left < right instead of left <= right.

D The function should return left instead of -1 when target is not found.

💡 Hint

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

Array indices go from 0 to length - 1. Using arr.length as right causes out-of-bound access.

🚀 Application

expert

Binary Search to Find First Occurrence in Sorted Array with Duplicates

Given a sorted array with duplicate elements, which iterative binary search modification correctly finds the index of the first occurrence of the target number?

DSA Typescript

function firstOccurrence(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  let result = -1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      result = mid;
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

const arr = [1, 2, 2, 2, 3, 4];
console.log(firstOccurrence(arr, 2));

A 2

B 3

C 1

D -1

💡 Hint

When you find the target, keep searching to the left to find the first occurrence.

The first occurrence of 2 is at index 1. The code updates result and moves right to mid - 1 to find earlier occurrences.