Binary Search as Divide and Conquer in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index in binary search.

DSA Typescript

const mid = Math.floor((low + [1]) / 2);

Drag options to blanks, or click blank then click option'

Ahigh

Bmid

Clow

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using mid instead of high causes incorrect calculation.

Using low twice results in always the same index.

The middle index is calculated by averaging low and high indices.

2fill in blank

medium

Complete the code to check if the middle element is the target.

DSA Typescript

if (arr[mid] === [1]) { return mid; }

Drag options to blanks, or click blank then click option'

Aarr

Bmid

Ctarget

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing arr[mid] with mid instead of target.

Using low or arr instead of target.

We compare the middle element with the target value to find a match.

3fill in blank

hard

Fix the error in updating the low index when target is greater than middle element.

DSA Typescript

if (arr[mid] < target) { low = [1]; }

Drag options to blanks, or click blank then click option'

Alow + 1

Bmid + 1

Cmid - 1

Dhigh - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting low to mid - 1 causes infinite loop or wrong search.

Using high or low + 1 incorrectly.

When target is greater, we move low to mid + 1 to search the right half.

4fill in blank

hard

Fill both blanks to update high index when target is less than middle element and to return -1 if not found.

DSA Typescript

if (arr[mid] > target) { [1] = mid - 1; } else if (low > high) { return [2]; }

Drag options to blanks, or click blank then click option'

Ahigh

B-1

Clow

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Updating low instead of high.

Returning 0 instead of -1 when not found.

When target is less, high moves to mid - 1. If low passes high, target is not found, so return -1.

5fill in blank

hard

Fill all three blanks to complete the recursive binary search function.

DSA Typescript

function binarySearch(arr: number[], target: number, low: number, high: number): number {
  if (low > high) return [1];
  const mid = Math.floor((low + [2]) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, [3]);
  else return binarySearch(arr, target, low, mid - 1);
}

Drag options to blanks, or click blank then click option'

A-1

Bhigh

Clow

Dmid

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of -1 in base case.

Using low instead of high in mid calculation.

Passing wrong high value in recursive call.

Return -1 if not found. Calculate mid using low and high. Search right half by updating low to mid + 1 and keeping high.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. Check every element one by one until the target is found

B. Use a hash table to find the target instantly

C. Sort the list first and then search linearly

D. Repeatedly split the sorted list into halves to find the target

Solution

1. Step 1: Understand binary search principle

   Binary search works by dividing the sorted list into two halves and deciding which half to continue searching in.

2. Step 2: Compare target with middle element

   By comparing the target with the middle element, we eliminate half the list each time, making search efficient.

3. Final Answer:

   Repeatedly split the sorted list into halves to find the target -> Option D

4. Quick Check:

   Divide and conquer = split list halves [OK]

Hint: Divide sorted list in halves to find target fast [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Searching linearly instead of dividing
• Ignoring the middle element comparison

2. Which of the following is the correct TypeScript function signature for a binary search function?

easy

A. function binarySearch(arr: number[], target: number): number

B. function binarySearch(arr: number, target: number[]): number

C. function binarySearch(arr: string[], target: string): void

D. function binarySearch(arr: number[], target: number): void

Solution

1. Step 1: Identify input and output types

   Binary search takes an array of numbers and a target number, returning the index (number) or -1 if not found.

2. Step 2: Match function signature

   function binarySearch(arr: number[], target: number): number matches input types (number array and number) and returns a number index, which is correct.

3. Final Answer:

   function binarySearch(arr: number[], target: number): number -> Option A

4. Quick Check:

   Input: number[], number; Output: number [OK]

Hint: Input array and target number, output index number [OK]

Common Mistakes:

• Swapping array and target types
• Returning void instead of index
• Using wrong array element types

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

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 nums = [2, 4, 6, 8, 10];
console.log(binarySearch(nums, 6));

medium

A. 2

B. 3

C. -1

D. 1

Solution

1. Step 1: Identify array and target

   Array is [2,4,6,8,10], target is 6.

2. Step 2: Trace binary search steps

   Middle index initially is 2 (value 6), which matches target, so function returns 2 immediately.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Find middle index and compare target [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Returning wrong index when target found

4. Identify the bug in this binary search implementation and choose the fix:

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;
}

medium

A. Change mid calculation to (left + right + 1) / 2

B. Change while condition to left < right

C. Change right initialization to arr.length - 1

D. Remove else if and use only if statements

Solution

1. Step 1: Check right boundary initialization

   Right should be last valid index, which is arr.length - 1, not arr.length (out of bounds).

2. Step 2: Understand impact on loop

   Using arr.length causes mid to sometimes be out of array range, causing runtime errors.

3. Final Answer:

   Change right initialization to arr.length - 1 -> Option C

4. Quick Check:

   Right boundary = last index [OK]

Hint: Right index must be last valid array index [OK]

Common Mistakes:

• Setting right to arr.length causes out-of-bounds
• Changing loop condition incorrectly
• Miscalculating mid index

5. You have a sorted array with duplicate values: [1, 2, 2, 2, 3, 4]. How would you modify binary search to find the first occurrence of 2?

hard

A. Search the right half after finding 2

B. After finding 2, continue searching left half to find earlier occurrence

C. Return the first found index immediately

D. Use linear search instead of binary search

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any matching index, not necessarily the first occurrence.

2. Step 2: Modify search to find first occurrence

   After finding target, continue searching left half to check if earlier occurrence exists, updating result accordingly.

3. Final Answer:

   After finding 2, continue searching left half to find earlier occurrence -> Option B

4. Quick Check:

   Find first occurrence by searching left side [OK]

Hint: Keep searching left after match to find first duplicate [OK]

Common Mistakes:

• Stopping at first found index
• Searching right half after match
• Switching to linear search unnecessarily