Binary Search vs Linear Search Real Cost Difference in DSA Typescript - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linear Search on an Unsorted Array

What is the output of the following TypeScript code that performs a linear search for the number 7 in an unsorted array?

DSA Typescript

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

const array = [3, 1, 4, 7, 5];
console.log(linearSearch(array, 7));

A -1

B 1

C 3

D 4

💡 Hint

Remember linear search checks elements one by one from the start.

The linear search checks each element until it finds 7 at index 3 (0-based). So it returns 3.

❓ Predict Output

intermediate

Output of Binary Search on a Sorted Array

What is the output of the following TypeScript code that performs a binary search for the number 7 in a sorted 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 = [1, 3, 4, 5, 7, 9];
console.log(binarySearch(array, 7));

A 4

B -1

C 3

D 5

💡 Hint

Binary search divides the array and finds the target index.

The number 7 is at index 4 in the sorted array, so binary search returns 4.

🧠 Conceptual

advanced

Cost Difference Between Linear and Binary Search

Which statement best describes the real cost difference between linear search and binary search when searching for an element in a large sorted array?

A Binary search is faster because it reduces the search space by half each step, while linear search checks every element one by one.

B Linear search is faster because it does not require the array to be sorted, unlike binary search.

C Both searches have the same cost because they both look at elements until they find the target.

D Binary search is slower because it requires more comparisons than linear search.

💡 Hint

Think about how many elements each search checks in the worst case.

Binary search cuts the search space in half each time, so it runs in logarithmic time, which is much faster than linear search's checking every element.

❓ Predict Output

advanced

Output of Binary Search on an Unsorted Array

What is the output of the following TypeScript code that performs a binary search for the number 7 on an unsorted 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 = [8, 9, 10, 1, 7];
console.log(binarySearch(array, 7));

A 0

B 2

C 4

D -1

💡 Hint

Binary search requires a sorted array to work correctly.

Since the array is unsorted, binary search cannot reliably find the target and returns -1.

🧠 Conceptual

expert

When Linear Search Can Be More Efficient Than Binary Search

In which scenario can linear search be more efficient than binary search despite binary search's better average time complexity?

A When the array is very large and sorted.

B When the array is very small or the target is near the beginning of the array.

C When the array is sorted and the target is near the end.

D When the array is sorted and contains only unique elements.

💡 Hint

Think about the overhead of binary search and the position of the target.

For small arrays or when the target is near the start, linear search can find the target faster because it checks elements sequentially without overhead.

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