Binary Search vs Linear Search Real Cost Difference in DSA Typescript - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a linear search that returns the index of the target or -1 if not found.

DSA Typescript

function linearSearch(arr: number[], target: number): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === [1]) {
      return i;
    }
  }
  return -1;
}

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

Atarget

Bi

Carr

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing arr[i] with i instead of target

Returning the element instead of the index

Using assignment '=' instead of comparison '==='

The linear search compares each element arr[i] with the target value to find a match.

2fill in blank

medium

Complete the code to perform a binary search on a sorted array and return the index of the target or -1 if not found.

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] [1] target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}

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

A===

B<

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causing wrong search direction

Using '!=' or '===' in the else if condition

Not updating left or right correctly

If the middle element is greater than the target, search the left half by moving right to mid - 1.

3fill in blank

hard

Fix the error in the binary search code to correctly calculate the middle index without overflow.

DSA Typescript

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = [1];
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}

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

AMath.floor((left + right) / 2)

BMath.ceil((left + right) / 2)

C(left + right) >> 1

Dleft + Math.floor((right - left) / 2)

Attempts:

3 left

💡 Hint

Common Mistakes

Using (left + right) / 2 directly causing overflow

Using Math.ceil which can cause infinite loops

Using bitwise shift which may be unclear

Using left + Math.floor((right - left) / 2) prevents overflow when left and right are large.

4fill in blank

hard

Complete the code to create a function that compares the number of steps taken by linear and binary search for a target in a sorted array.

DSA Typescript

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

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

A>

B<

C,

D;

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in binary search comparison

Using semicolon instead of comma in object return

Not incrementing step counters

5fill in blank

hard

Fill all three blanks to create a function that measures and prints the time taken by linear and binary search to find a target in a sorted array.

DSA Typescript

function measureSearchTime(arr: number[], target: number): void {
  const startLinear = performance.now();
  linearSearch(arr, target);
  const endLinear = performance.now();
  const startBinary = performance.now();
  binarySearch(arr, target);
  const endBinary = performance.now();
  console.log('Linear Search Time: ' + (endLinear [1] startLinear) + ' ms');
  console.log('Binary Search Time: ' + (endBinary [2] startBinary) + ' ms');
  console.log('Binary search is approximately ' + ((endLinear [3] startLinear) / (endBinary [2] startBinary)).toFixed(2) + ' times faster');
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '-' causing incorrect time calculation

Using multiplication or division instead of subtraction

Mixing operators inconsistently

Subtract start time from end time to get elapsed time; use subtraction for both searches and for ratio calculation.

Practice

1. Which search algorithm is generally faster on a sorted list of 1,000,000 elements?

easy

A. Linear Search

B. Both are equally fast

C. Binary Search

D. Neither works on sorted lists

Solution

1. Step 1: Understand the search algorithms

   Binary Search divides the list in half repeatedly, while Linear Search checks each element one by one.

2. Step 2: Compare efficiency on large sorted lists

   Binary Search takes about log2(1,000,000) ≈ 20 steps, Linear Search takes up to 1,000,000 steps.

3. Final Answer:

   Binary Search -> Option C

4. Quick Check:

   Binary Search is faster on sorted lists [OK]

Hint: Binary Search halves search space; Linear checks all [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted lists
• Confusing sorted and unsorted list requirements
• Ignoring the difference in step counts

2. Which of the following is the correct TypeScript syntax to perform a linear search on an array arr for a value target?

easy

A. arr.findIndex(target);

B. for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; }

C. while (arr.includes(target)) { return arr.indexOf(target); }

D. for (let i in arr) { if (arr[i] == target) return i; }

Solution

1. Step 1: Check syntax for linear search loop

   for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; } uses a for loop with index and compares each element to target correctly.

2. Step 2: Analyze other options for correctness

   while (arr.includes(target)) { return arr.indexOf(target); } misuses while with includes; arr.findIndex(target); uses findIndex incorrectly; for (let i in arr) { if (arr[i] == target) return i; } uses 'in' which iterates keys but with loose equality.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; } -> Option B

4. Quick Check:

   Correct for loop syntax for linear search [OK]

Hint: Use for loop with strict equality for linear search [OK]

Common Mistakes:

• Using while loop incorrectly
• Using loose equality (==) instead of strict (===)
• Misusing array methods for search

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

const arr = [1, 3, 5, 7, 9];
function binarySearch(array: number[], target: number): number {
  let left = 0;
  let right = array.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (array[mid] === target) return mid;
    else if (array[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
console.log(binarySearch(arr, 7));

medium

A. 3

B. 2

C. -1

D. 4

Solution

1. Step 1: Trace binary search steps for target 7

   Initial left=0, right=4, mid=2 (value 5). 5 < 7, so left=3.

2. Step 2: Next iteration mid=3 (value 7), matches target, return 3

   The function returns index 3 where 7 is found.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Index of 7 in array is 3 [OK]

Hint: Calculate mid index and compare stepwise [OK]

Common Mistakes:

• Confusing mid calculation
• Returning wrong index
• Not updating left/right correctly

4. Identify the bug in this linear search function and select the fix:

function linearSearch(arr: number[], target: number): number {
  for (let i = 0; i <= arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

medium

A. Change loop condition to i < arr.length

B. Change === to == in if condition

C. Add a break after return statement

D. Initialize i to 1 instead of 0

Solution

1. Step 1: Analyze loop condition

   The loop runs while i <= arr.length, which causes out-of-bounds access at i = arr.length.

2. Step 2: Fix loop condition to prevent error

   Changing to i < arr.length ensures valid indices only.

3. Final Answer:

   Change loop condition to i < arr.length -> Option A

4. Quick Check:

   Loop must stay within array bounds [OK]

Hint: Use i < arr.length to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loop
• Changing equality operator unnecessarily
• Adding break after return (unreachable code)

5. You have a sorted array of 10,000 elements and want to find a target value. Which approach minimizes the average number of comparisons, and why?

Options:
A) Use Linear Search because it checks elements sequentially.
B) Use Linear Search but start from the middle.
C) Use Binary Search but only check every other element.
D) Use Binary Search because it divides the search space each step.

hard

A. Use Linear Search because it checks elements sequentially.

B. Use Linear Search but start from the middle.

C. Use Binary Search but only check every other element.

D. Use Binary Search because it divides the search space each step.

Solution

1. Step 1: Understand average comparisons for Linear vs Binary Search

   Linear Search averages about n/2 = 5,000 comparisons; Binary Search averages about log2(10,000) ≈ 14 comparisons.

2. Step 2: Evaluate options for efficiency

   Binary Search halves search space each step, minimizing comparisons. Starting Linear Search from middle or skipping elements breaks correctness or efficiency.

3. Final Answer:

   Use Binary Search because it divides the search space each step. -> Option D

4. Quick Check:

   Binary Search minimizes comparisons on sorted arrays [OK]

Hint: Binary Search halves search space, fewer comparisons [OK]

Common Mistakes:

• Thinking linear search is faster on sorted arrays
• Starting linear search from middle doesn't help
• Skipping elements in binary search breaks correctness