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

Concept Flow - Binary Search vs Linear Search Real Cost Difference

Start Search

↓

Choose Search Type

↓

Linear

↓

Check each

↓

Found?

No→Adjust range

↓

Return

Yes↓

Return

↓

Adjust range

↓

Repeat

↓

Not Found

↓

Return

Shows the choice between linear and binary search and their step-by-step decision process.

Execution Sample

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

function binarySearch(arr: number[], target: number): number {
  let left = 0, 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 = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Linear search checks each element one by one; binary search divides the search range in half each step.

Execution Table

Step	Operation	Index Checked	Comparison Result	Pointer Changes	Visual State
1	Linear Search Start	None	N/A	i=0	[5, 8, 12, 20, 25]
2	Check arr[0]	0	5 == 20? No	i=1	[5, 8, 12, 20, 25]
3	Check arr[1]	1	8 == 20? No	i=2	[5, 8, 12, 20, 25]
4	Check arr[2]	2	12 == 20? No	i=3	[5, 8, 12, 20, 25]
5	Check arr[3]	3	20 == 20? Yes	Found at 3	[5, 8, 12, 20, 25]
6	Linear Search End	3	Found target	Return 3	[5, 8, 12, 20, 25]
7	Binary Search Start	None	N/A	left=0, right=4	[5, 8, 12, 20, 25]
8	Calculate mid	2	arr[2]=12	mid=2	[5, 8, 12, 20, 25]
9	Compare arr[2]	2	12 == 20? No	left=3, right=4	[5, 8, 12, 20, 25]
10	Adjust left	3	left=3	left=3, right=4	[5, 8, 12, 20, 25]
11	Calculate mid	3	arr[3]=20	mid=3	[5, 8, 12, 20, 25]
12	Compare arr[3]	3	20 == 20? Yes	Found at 3	[5, 8, 12, 20, 25]
13	Binary Search End	3	Found target	Return 3	[5, 8, 12, 20, 25]
14	Linear Search Worst Case	4	25 == 30? No	i=5	[5, 8, 12, 20, 25]
15	Linear Search End	None	Target not found	Return -1	[5, 8, 12, 20, 25]
16	Binary Search Worst Case Start	None	N/A	left=0, right=4	[5, 8, 12, 20, 25]
17	Calculate mid	2	arr[2]=12	mid=2	[5, 8, 12, 20, 25]
18	Compare arr[2]	2	12 == 30? No	left=3, right=4	[5, 8, 12, 20, 25]
19	Calculate mid	3	arr[3]=20	mid=3	[5, 8, 12, 20, 25]
20	Compare arr[3]	3	20 == 30? No	left=4, right=4	[5, 8, 12, 20, 25]
21	Calculate mid	4	arr[4]=25	mid=4	[5, 8, 12, 20, 25]
22	Compare arr[4]	4	25 == 30? No	left=4, right=3	[5, 8, 12, 20, 25]
23	Binary Search End	None	Target not found	Return -1	[5, 8, 12, 20, 25]

💡 Search ends when target is found or search range is empty (left > right).

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 7	After Step 10	After Step 11	After Step 14	After Step 18	After Step 21	Final
i (Linear Search)	0	1	3	3 (found)	N/A	N/A	N/A	5 (end)	N/A	N/A	N/A
left (Binary Search)	N/A	N/A	N/A	N/A	0	3	3	0	3	4	4
right (Binary Search)	N/A	N/A	N/A	N/A	4	4	4	4	4	4	3
mid (Binary Search)	N/A	N/A	N/A	N/A	2	2	3	2	3	4	N/A

Key Moments - 3 Insights

Why does binary search adjust 'left' or 'right' pointers instead of checking every element?

Binary search divides the search range in half each time by adjusting 'left' or 'right' pointers, reducing the number of checks needed. This is shown in steps 9, 10, 18, and 22 where pointers move instead of checking all elements.

Why does linear search sometimes take more steps than binary search?

Linear search checks each element one by one until it finds the target or reaches the end, as seen in steps 2 to 5 and 14. Binary search quickly narrows down the search range, so it usually takes fewer steps, shown in steps 7 to 13.

What happens when the target is not in the array?

Both searches return -1 when the target is not found. Linear search ends after checking all elements (step 15), binary search ends when 'left' pointer passes 'right' (step 23).

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'mid' at step 11 during binary search?

A 3

B 2

C 4

D 1

💡 Hint

Check the 'mid (Binary Search)' row in variable_tracker after step 11.

At which step does linear search find the target 20?

A Step 3

B Step 5

C Step 6

D Step 4

💡 Hint

Look at the 'Comparison Result' column in execution_table for linear search steps.

If the target was the first element (5), how would linear search's 'i' variable change in the execution table?

A It would return at i=0

B It would check all elements

C It would return at i=1

D It would never find the target

💡 Hint

Linear search returns immediately when it finds the target, as shown in steps 2-5.

Concept Snapshot

Binary Search vs Linear Search:
- Linear Search checks each element one by one.
- Binary Search divides search range in half each step.
- Binary Search requires sorted array.
- Linear Search works on any array.
- Binary Search is faster for large sorted arrays.
- Linear Search is simple but slower for big data.

Full Transcript

This visual compares linear and binary search methods. Linear search checks each element from start to end until it finds the target or finishes the list. Binary search works only on sorted arrays and repeatedly checks the middle element, adjusting the search range by moving left or right pointers. The execution table shows step-by-step how each search checks elements and updates pointers. Variable tracker shows how indexes and pointers change. Key moments clarify why binary search adjusts pointers instead of checking all elements, why linear search can take more steps, and what happens when the target is not found. The quiz tests understanding of mid calculation, step when target is found, and behavior if target is first element. The snapshot summarizes the main differences and use cases.

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