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

Concept Flow - Binary Search vs Linear Search Real Cost Difference

Start at index 0

↓

Check element == target?

No→Move to next index

↓

Reached end?

Yes→Not found

↓

Found

↓

Start with low=0, high=n-1

↓

Calculate mid = (low+high)/2

↓

Check element at mid == target?

↓

Found

↓

Repeat until low > high

↓

Not found

Linear search checks each element one by one until it finds the target or ends. Binary search splits the search range in half each time, quickly narrowing down where the target could be.

Execution Sample

DSA C#

int LinearSearch(int[] arr, int target) {
  for (int i = 0; i < arr.Length; i++) {
    if (arr[i] == target) return i;
  }
  return -1;
}

int BinarySearch(int[] arr, int target) {
  int low = 0, high = arr.Length - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

This code shows linear search scanning each element, and binary search dividing the search range until it finds the target or ends.

Execution Table

Step	Search Type	Operation	Index Checked	Comparison Result	Pointer Changes	Visual State
1	Linear	Check element	0	arr[0] != target	i=1	[5, 8, 12, 20, 25] (i=0)
2	Linear	Check element	1	arr[1] != target	i=2	[5, 8, 12, 20, 25] (i=1)
3	Linear	Check element	2	arr[2] == target	Found at i=2	[5, 8, 12, 20, 25] (i=2)
4	Binary	Calculate mid	-	-	low=0, high=4, mid=2	[5, 8, 12, 20, 25] (mid=2)
5	Binary	Compare mid element	2	arr[2] == target	Found at mid=2	[5, 8, 12, 20, 25] (mid=2)
6	Linear	Check element	0	arr[0] != target	i=1	[5, 8, 12, 20, 25] (i=0)
7	Linear	Check element	1	arr[1] != target	i=2	[5, 8, 12, 20, 25] (i=1)
8	Linear	Check element	2	arr[2] != target	i=3	[5, 8, 12, 20, 25] (i=2)
9	Linear	Check element	3	arr[3] != target	i=4	[5, 8, 12, 20, 25] (i=3)
10	Linear	Check element	4	arr[4] != target	i=5	[5, 8, 12, 20, 25] (i=4)
11	Linear	End	-	Not found	-	[5, 8, 12, 20, 25] (end)
12	Binary	Calculate mid	-	-	low=0, high=4, mid=2	[5, 8, 12, 20, 25] (low=0, high=4, mid=2)
13	Binary	Compare mid element	2	arr[2] < target	low=mid+1=3	[5, 8, 12, 20, 25] (low=3, high=4)
14	Binary	Calculate mid	-	-	low=3, high=4, mid=3	[5, 8, 12, 20, 25] (low=3, high=4, mid=3)
15	Binary	Compare mid element	3	arr[3] < target	low=mid+1=4	[5, 8, 12, 20, 25] (low=4, high=4, mid=3)
16	Binary	Calculate mid	-	-	low=4, high=4, mid=4	[5, 8, 12, 20, 25] (low=4, high=4, mid=4)
17	Binary	Compare mid element	4	arr[4] < target	low=mid+1=5	[5, 8, 12, 20, 25] (low=5, high=4)
18	Binary	End	-	Not found (low > high)	-	[5, 8, 12, 20, 25] (end)

💡 Linear search stops when index reaches array length or target found; binary search stops when low > high or target found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Linear i	0	1	2	Found at 2	-	-	2
Binary low	0	0	0	0	0	0	0
Binary high	4	4	4	4	4	4	4
Binary mid	-	-	-	-	2	2	2

Key Moments - 3 Insights

Why does binary search calculate mid each time instead of checking all elements?

Binary search cuts the search range in half each time by calculating mid, so it quickly narrows down where the target could be. This is shown in execution_table rows 12-17 where mid changes and low/high pointers move.

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 ends. If the target is near the end or not present, it checks many elements (rows 6-11). Binary search uses fewer steps by dividing the search range (rows 12-18).

What happens when the target is not in the array?

Linear search checks all elements and ends when index reaches array length (row 11). Binary search ends when low pointer passes high pointer (row 18). Both return 'not found' but binary search does it faster.

Visual Quiz - 3 Questions

Look at the execution_table, at which step does linear search find the target?

A Step 2

B Step 3

C Step 5

D Step 11

💡 Hint

Check the 'Search Type' and 'Comparison Result' columns for linear search finding target.

At which step does binary search update the low pointer to 3?

A Step 14

B Step 15

C Step 13

D Step 17

💡 Hint

Look at 'Pointer Changes' column for binary search steps where low changes.

If the target was the first element, how would linear search steps change?

A It would find target at step 1

B It would find target at step 3

C It would take all steps to end

D It would not find target

💡 Hint

Look at linear search steps and when it finds target at index 0.

Concept Snapshot

Linear Search:
- Checks each element one by one
- Time: O(n) worst case

Binary Search:
- Requires sorted array
- Divides search range by half each step
- Time: O(log n) worst case

Binary search is faster but needs sorted data.

Full Transcript

This lesson compares linear and binary search by showing how each checks elements step-by-step. Linear search starts at the first element and checks each one until it finds the target or ends. Binary search starts with the whole array, calculates the middle, and compares the target to the middle element. It then narrows the search range by moving low or high pointers, repeating until it finds the target or the range is empty. The execution table shows linear search checking elements in order, while binary search jumps to midpoints. Variable tracking shows how pointers change. Key moments explain why binary search calculates mid each time, why linear search can take more steps, and what happens when the target is missing. The quiz tests understanding of these steps. The snapshot summarizes the main differences and costs.

Practice

1. Which search algorithm generally performs faster on a sorted list of 1,000,000 elements?

easy

A. Binary Search

B. Linear Search

C. Both perform equally

D. Depends on the element position only

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 performance on large sorted lists

   Binary Search runs in O(log n) time, which is much faster than Linear Search's O(n) time for large n.

3. Final Answer:

   Binary Search -> Option A

4. Quick Check:

   Binary Search faster on sorted large lists [OK]

Hint: Binary Search halves list each step, faster on sorted data [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted lists
• Ignoring the sorted list requirement for Binary Search
• Confusing average and worst-case times

2. Which of the following is the correct syntax to perform a linear search for value target in an integer array arr in C#?

easy

A. foreach (int i in arr) { if (i == target) return i; }

B. for (int i = 1; i <= arr.Length; i++) { if (arr[i] == target) return i; }

C. for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; }

D. while (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; }

Solution

1. Step 1: Check loop initialization and condition

   for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } correctly initializes i at 0 and loops while i is less than arr.Length, which is valid for array indexing.

2. Step 2: Verify element access and comparison

   for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } accesses arr[i] correctly and compares it to target, returning index if found.

3. Final Answer:

   for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } -> Option C

4. Quick Check:

   Correct for-loop syntax for linear search [OK]

Hint: Array indices start at 0; loop till less than length [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < in loop condition
• Incorrect loop syntax like while with initialization

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

int[] arr = {2, 4, 6, 8, 10};
int target = 6;
int index = -1;

// Linear Search
for (int i = 0; i < arr.Length; i++) {
    if (arr[i] == target) {
        index = i;
        break;
    }
}
Console.WriteLine(index);

medium

A. 2

B. 3

C. -1

D. 0

Solution

1. Step 1: Trace the loop to find target in array

   Array elements: 2(0), 4(1), 6(2), 8(3), 10(4). Loop checks each index until arr[i] == 6 at i=2.

2. Step 2: Assign index and break loop

   When found at i=2, index is set to 2 and loop breaks.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Index of target in array is position starting at 0 [OK]

Common Mistakes:

• Confusing value with index
• Off-by-one errors in indexing
• Not breaking loop after finding target

4. The following code attempts to perform a binary search on a sorted array but has a bug. What is the bug?

int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

medium

A. Loop condition should be left < right

B. Array must be unsorted for binary search

C. Should return mid + 1 when found

D. Mid calculation can cause integer overflow

Solution

1. Step 1: Analyze mid calculation

   Mid is calculated as (left + right) / 2, which can overflow if left and right are large integers.

2. Step 2: Suggest safe mid calculation

   Use mid = left + (right - left) / 2 to avoid overflow.

3. Final Answer:

   Mid calculation can cause integer overflow -> Option D

4. Quick Check:

   Mid overflow risk in binary search [OK]

Hint: Use safe mid calculation to avoid overflow [OK]

Common Mistakes:

• Ignoring integer overflow in mid calculation
• Changing loop condition incorrectly
• Misunderstanding binary search requires sorted array

5. You have a sorted array of 1,000,000 integers and want to find if a number exists. You also know that the number is more likely to be near the start of the array. Which search method minimizes average search cost and why?

hard

A. Binary Search, because it always halves the search space

B. Linear Search, because it finds elements near the start faster

C. Binary Search, because it is faster for all positions

D. Linear Search, because it uses less memory

Solution

1. Step 1: Consider element distribution and search costs

   Binary Search takes O(log n) steps regardless of element position. Linear Search takes fewer steps if element is near start.

2. Step 2: Compare average costs given element likely near start

   Since element is likely near start, Linear Search will find it quickly on average, minimizing cost.

3. Final Answer:

   Linear Search, because it finds elements near the start faster -> Option B

4. Quick Check:

   Element near start favors Linear Search [OK]

Hint: Near start? Linear Search is faster on average [OK]

Common Mistakes:

• Assuming Binary Search always fastest
• Ignoring element distribution impact
• Confusing memory use with speed