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.