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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search on Sorted Array

What is the output of the following TypeScript code that uses recursive binary search to find the index of the target value 7?

DSA Typescript

function binarySearch(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) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

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

A -1

B 3

C 2

D 4

💡 Hint

Think about the position of 7 in the sorted array and how binary search divides the array.

The array is [1, 3, 5, 7, 9, 11]. The target 7 is at index 3 (0-based). The recursive binary search finds it and returns 3.

❓ Predict Output

intermediate

Result when target is not in the array

What does the recursive binary search function return when searching for the target value 8 in the array [2, 4, 6, 10, 12]?

DSA Typescript

function binarySearch(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) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

const array = [2, 4, 6, 10, 12];
const result = binarySearch(array, 8, 0, array.length - 1);
console.log(result);

A -1

B 2

C 3

D 0

💡 Hint

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

The target 8 is not in the array. The recursive calls eventually cross over (left > right), so the function returns -1.

🧠 Conceptual

advanced

Understanding Recursive Call Depth in Binary Search

If you perform a recursive binary search on a sorted array of 64 elements, what is the maximum number of recursive calls that can happen before the search ends?

A 6

B 64

C 7

D 8

💡 Hint

Binary search divides the array size by 2 each call. Think about powers of 2.

Binary search halves the search space each call. For 64 elements (2^6), the worst-case recursion depth is log₂(64) + 1 = 7 calls total (6 recursive calls + initial).

🔧 Debug

advanced

Identify the error in this recursive binary search implementation

What error will this TypeScript recursive binary search code produce when searching for target 7 in array [1, 3, 5, 7]?

DSA Typescript

function binarySearch(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) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}

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

A Returns -1 even though target exists

B Throws a runtime error due to infinite recursion

C Returns the wrong index (off by one)

D Returns the correct index 2

💡 Hint

Check the base case condition carefully.

The base case uses 'left >= right' which causes the function to return -1 prematurely when left equals right, missing the last element check. So it returns -1 even if the target is present.

🚀 Application

expert

Find the first occurrence of a target in a sorted array with duplicates using recursive binary search

Given a sorted array with duplicates, which recursive binary search modification correctly returns the index of the first occurrence of the target value 4 in [1, 2, 4, 4, 4, 5, 6]?

DSA Typescript

function firstOccurrence(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 mid;
    else return firstOccurrence(arr, target, left, mid - 1);
  } else if (arr[mid] < target) {
    return firstOccurrence(arr, target, mid + 1, right);
  } else {
    return firstOccurrence(arr, target, left, mid - 1);
  }
}

const array = [1, 2, 4, 4, 4, 5, 6];
const result = firstOccurrence(array, 4, 0, array.length - 1);
console.log(result);

A -1

B 3

C 4

D 2

💡 Hint

Check if the found target is the first or if you need to search left side.

The function finds the first index where 4 appears by checking if the previous element is less than 4 or if it's the first element. The first occurrence of 4 is at index 2.