Binary Search vs Linear Search Real Cost Difference in DSA Typescript - Trade-offs & Analysis

Mental Model

Binary search quickly finds a number by cutting the search area in half each time, while linear search checks each number one by one.

Analogy: Imagine looking for a name in a phone book: linear search is like checking every name from start to end, binary search is like opening the book in the middle and deciding which half to look next.

Array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> null
Linear Search: ↑ starts at index 0
Binary Search: ↑ starts checking middle index

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13, 15], search for value 9

Goal: Show how many steps each search takes to find 9 and compare their costs

Step 1: Linear search checks first element (1)

[1↑] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> null

Why: Linear search starts from the beginning and checks each element

Step 2: Linear search checks second element (3)

[1] -> [3↑] -> [5] -> [7] -> [9] -> [11] -> [13] -> [15] -> null

Why: Value not found yet, move to next element

Step 3: Linear search checks third element (5)

[1] -> [3] -> [5↑] -> [7] -> [9] -> [11] -> [13] -> [15] -> null

Why: Keep checking sequentially

Step 4: Linear search checks fourth element (7)

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> [15] -> null

Why: Still not found, continue

Step 5: Linear search checks fifth element (9) and finds it

[1] -> [3] -> [5] -> [7] -> [9↑] -> [11] -> [13] -> [15] -> null

Why: Found the target value after 5 checks

Step 6: Binary search checks middle element (index 3, value 7)

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> [15] -> null

Why: Binary search starts by checking the middle element

Step 7: Since 9 > 7, binary search moves to right half: indexes 4 to 7

[9] -> [11] -> [13] -> [15] with middle at index 5

Why: Discard left half because target is greater than middle

Step 8: Binary search checks middle of right half (index 5, value 11)

[9] -> [11↑] -> [13] -> [15]

Why: Check new middle to narrow down search

Step 9: Since 9 < 11, binary search moves to left half: index 4

[9↑]

Why: Discard right half because target is less than middle

Step 10: Binary search checks index 4 and finds 9

[9↑]

Why: Found the target value after 3 checks

Result:

Linear search final state: 1 -> 3 -> 5 -> 7 -> 9↑ -> 11 -> 13 -> 15 -> null (found after 5 checks)
Binary search final state: 1 -> 3 -> 5 -> 7 -> 9↑ -> 11 -> 13 -> 15 -> null (found after 3 checks)

Annotated Code

DSA Typescript

class Search {
  static linearSearch(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === target) {
        return i; // found target
      }
    }
    return -1; // not found
  }

  static 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; // found target
      } else if (arr[mid] < target) {
        left = mid + 1; // search right half
      } else {
        right = mid - 1; // search left half
      }
    }
    return -1; // not found
  }
}

const arr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 9;

const linearIndex = Search.linearSearch(arr, target);
console.log(`Linear Search found ${target} at index: ${linearIndex}`);

const binaryIndex = Search.binarySearch(arr, target);
console.log(`Binary Search found ${target} at index: ${binaryIndex}`);

if (arr[i] === target) { return i; }

check each element sequentially until target found

while (left <= right) { const mid = Math.floor((left + right) / 2);

calculate middle index to split search range

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

check if middle element is target

else if (arr[mid] < target) { left = mid + 1; }

move left pointer to right half if target is greater

else { right = mid - 1; }

move right pointer to left half if target is smaller

Output

Linear Search found 9 at index: 4

Binary Search found 9 at index: 4

Complexity Analysis

Time: O(n) for linear search because it may check every element; O(log n) for binary search because it halves the search space each step

Space: O(1) for both because they use only a few variables regardless of input size

vs Alternative: Binary search is much faster on sorted data than linear search, especially for large arrays, but requires the array to be sorted first

Edge Cases

empty array

both searches return -1 immediately because there is nothing to check

DSA Typescript

for (let i = 0; i < arr.length; i++) {

target not in array

both searches return -1 after checking all possible elements or ranges

DSA Typescript

return -1; // not found

array with one element equal to target

both searches find the target immediately at index 0

DSA Typescript

if (arr[i] === target) { return i; }

When to Use This Pattern

When you need to find an item in a sorted list quickly, reach for binary search because it reduces the search area by half each step, unlike linear search which checks one by one.

Common Mistakes

Mistake: Trying binary search on an unsorted array
Fix: Sort the array first or use linear search instead

Mistake: Using wrong mid calculation causing infinite loop
Fix: Calculate mid as Math.floor((left + right) / 2) to avoid errors

Summary

Binary search finds an item by repeatedly dividing the search range in half, while linear search checks each item one by one.

Use binary search when the data is sorted and you want faster search times; use linear search when data is unsorted or small.

The key insight is that binary search cuts the search space quickly, making it much faster than linear search on large sorted lists.

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