Binary Search vs Linear Search Real Cost Difference in DSA Javascript - 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 Javascript

function linearSearch(arr, target) {
  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'

Aindex

Bi

Carr

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Using the loop index 'i' instead of the target for comparison.

Comparing arr[i] with arr instead of target.

The function 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 to find the target index or return -1 if not found.

DSA Javascript

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

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

Amid

Bright

Ctarget

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing arr[mid] with mid instead of target.

Using left or right instead of target for comparison.

The binary search compares the middle element arr[mid] with the target to decide the search direction.

3fill in blank

hard

Fix the error in the binary search code to correctly update the search boundaries.

DSA Javascript

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

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

Amid + 1

Bmid - 1

Cleft + 1

Dright - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting left to mid - 1 which moves left boundary incorrectly.

Using right - 1 or left + 1 which are not correct updates here.

When arr[mid] is less than target, we move the left boundary to mid + 1 to search the right half.

4fill in blank

hard

Fill both blanks to create a function that compares the number of steps taken by linear and binary search to find a target.

DSA Javascript

function compareSearches(arr, target) {
  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++;
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      break;
    } else if (arr[mid] < target) {
      left = [1];
    } else {
      right = [2];
    }
  }

  return { linearSteps, binarySteps };
}

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

Amid + 1

Bmid - 1

Cleft + 1

Dright - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the updates of left and right boundaries.

Using left + 1 or right - 1 incorrectly.

In binary search, when arr[mid] < target, left moves to mid + 1; when arr[mid] > target, right moves to mid - 1.

5fill in blank

hard

Fill all three blanks to create a function that returns the search method with fewer steps for a given target.

DSA Javascript

function bestSearchMethod(arr, target) {
  const { linearSteps, binarySteps } = compareSearches(arr, target);
  if (linearSteps [1] binarySteps) {
    return [2];
  } else {
    return [3];
  }
}

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

A<

B>

C"Linear Search"

D"Binary Search"

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < in the if condition.

Returning the wrong search method string.

If linearSteps is less than binarySteps, return "Linear Search"; otherwise, return "Binary Search".

Practice

1. Which search method is generally faster for finding an element in a sorted list of 1,000,000 items?

easy

A. Binary Search

B. Linear Search

C. Both are equally fast

D. Neither works on sorted lists

Solution

1. Step 1: Understand search methods on sorted lists

   Binary Search divides the list repeatedly, reducing search space quickly. Linear Search checks each item one by one.

2. Step 2: Compare efficiency on large sorted lists

   Binary Search runs in about log2(1,000,000) ≈ 20 steps, Linear Search may take up to 1,000,000 steps.

3. Final Answer:

   Binary Search -> Option A

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 efficiency
• Ignoring logarithmic speed of Binary Search

2. Which of the following is the correct syntax to start a binary search on a sorted array arr in JavaScript?

easy

A. let mid = (start + end) / 2;

B. let mid = start - end;

C. let mid = start + end;

D. let mid = Math.floor((start + end) / 2);

Solution

1. Step 1: Calculate middle index correctly

   Binary Search finds middle by averaging start and end indices, then flooring to get integer index.

2. Step 2: Check each option for correctness

   let mid = Math.floor((start + end) / 2); uses Math.floor to get integer mid index; others either don't floor or use wrong operations.

3. Final Answer:

   let mid = Math.floor((start + end) / 2); -> Option D

4. Quick Check:

   Floor average of start and end gives mid [OK]

Hint: Use Math.floor to get integer middle index [OK]

Common Mistakes:

• Not using Math.floor causing float index
• Adding or subtracting indices incorrectly
• Using mid as sum without division

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

const arr = [2, 4, 6, 8, 10];
function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}
console.log(linearSearch(arr, 8));

medium

A. -1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace the linear search loop

   The function checks each element: arr[0]=2, arr[1]=4, arr[2]=6, arr[3]=8 matches target 8.

2. Step 2: Return index when target found

   At index 3, target 8 is found, so function returns 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Index of 8 in array is 3 [OK]

Hint: Linear search returns index of first match [OK]

Common Mistakes:

• Returning value instead of index
• Off-by-one errors in loop
• Confusing index with element value

4. The following binary search code has a bug. What is the error?

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) start = mid + 1;
    else end = mid - 1;
  }
  return -1;
}

medium

A. end should be initialized to arr.length - 1

B. start should be initialized to 1

C. mid calculation is incorrect

D. Loop condition should be start < end

Solution

1. Step 1: Check initialization of end index

   Array indices go from 0 to arr.length - 1, so end must be arr.length - 1 to avoid out-of-bounds.

2. Step 2: Understand loop condition and mid usage

   With end = arr.length, mid can be arr.length which is invalid index, causing error.

3. Final Answer:

   end should be initialized to arr.length - 1 -> Option A

4. Quick Check:

   Array last index = length - 1 [OK]

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

Common Mistakes:

• Setting end to arr.length causing index error
• Changing start incorrectly
• Using wrong loop condition

5. You have a sorted array of 1,000,000 numbers and want to find if the number 500,000 exists. Which search method will minimize the average number of comparisons, and why?

hard

A. Linear Search, because it checks elements sequentially

B. Binary Search, because it reduces search space by half each step

C. Linear Search, because it is simpler to implement

D. Binary Search, but only if the array is unsorted

Solution

1. Step 1: Analyze search methods on large sorted arrays

   Linear Search checks elements one by one, averaging 500,000 comparisons for half the array.

2. Step 2: Understand Binary Search efficiency

   Binary Search halves the search space each step, needing about log2(1,000,000) ≈ 20 comparisons.

3. Step 3: Compare average comparisons

   20 comparisons (Binary Search) is much less than 500,000 (Linear Search), so Binary Search is better.

4. Final Answer:

   Binary Search, because it reduces search space by half each step -> Option B

5. Quick Check:

   Binary Search uses log steps, fewer comparisons [OK]

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

Common Mistakes:

• Choosing Linear Search for sorted arrays
• Ignoring logarithmic speed advantage
• Thinking Binary Search needs sorted array but choosing wrong option