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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

What is the output of the following TypeScript code that performs binary search on a sorted array to find the index of the number 7?

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 array = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(array, 7));

A 2

B 3

C -1

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 3.

❓ Predict Output

intermediate

Binary Search Result When Target Not Present

What will the following TypeScript binary search function return when searching for 8 in the 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 array = [2, 4, 6, 10, 12];
console.log(binarySearch(array, 8));

A -1

B 2

C 3

D 0

💡 Hint

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

Since 8 is not in the array, the binary search returns -1 indicating the target is absent.

🔧 Debug

advanced

Identify the Error in Binary Search Implementation

What error will occur when running this TypeScript binary search code?

DSA Typescript

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length;
  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 = [1, 2, 3, 4, 5];
console.log(binarySearch(array, 3));

A SyntaxError: Unexpected token

B Returns 2

C RangeError: Maximum call stack size exceeded

D TypeError: Cannot read property '3' of undefined

💡 Hint

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

The right pointer is set to arr.length which is out of bounds for array indexing (max index is length - 1). Accessing arr[mid] when mid equals arr.length causes undefined access leading to TypeError.

🧠 Conceptual

advanced

Why Binary Search is Divide and Conquer

Which statement best explains why binary search is considered a divide and conquer algorithm?

A It merges two sorted arrays into one sorted array.

B It checks every element one by one until it finds the target.

C It divides the array into two halves and recursively searches only one half where the target can be.

D It sorts the array before searching for the target.

💡 Hint

Divide and conquer means breaking the problem into smaller parts and solving one part.

Binary search splits the array into halves and searches only the half that may contain the target, reducing the problem size each step.

❓ Predict Output

expert

Output of Recursive Binary Search with Duplicate Elements

What is the output of the following TypeScript recursive binary search code when searching for 5 in the array with duplicates?

DSA Typescript

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

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

A 2

B 3

C 4

D -1

💡 Hint

The function returns the first occurrence index of the target.

The code searches recursively to find the first index where 5 appears, which is index 2.