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

↓

Index < array size?

No→Not found

↓

Found element

↓

Repeat check

↓

Start with low=0, high=n-1

↓

Calculate mid = (low+high)/2

↓

Check element at mid == target?

↓

Found

↓

high = mid-1

↓

low <= high?

No→Not found

Linear search checks each element one by one until it finds the target or ends. Binary search repeatedly splits the sorted array in half to find the target faster.

Execution Sample

DSA C++

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

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

Linear search scans each element until it finds the target. Binary search divides the sorted array to find the target faster.

Execution Table

Step	Operation	Index Checked / Mid	Condition	Action	Visual State
1	Linear Search start	Index=0	arr[0] == 7?	No, move to next	[3, 5, 7, 9, 11]
2	Linear Search	Index=1	arr[1] == 7?	No, move to next	[3, 5, 7, 9, 11]
3	Linear Search	Index=2	arr[2] == 7?	Yes, found target	[3, 5, 7, 9, 11]
4	Binary Search start	low=0, high=4	Calculate mid=2	Check arr[2] == 7?	[3, 5, 7, 9, 11]
5	Binary Search	mid=2	arr[2] == 7?	Yes, found target	[3, 5, 7, 9, 11]
6	Linear Search start	Index=0	arr[0] == 12?	No, move to next	[3, 5, 7, 9, 11]
7	Linear Search	Index=1	arr[1] == 12?	No, move to next	[3, 5, 7, 9, 11]
8	Linear Search	Index=2	arr[2] == 12?	No, move to next	[3, 5, 7, 9, 11]
9	Linear Search	Index=3	arr[3] == 12?	No, move to next	[3, 5, 7, 9, 11]
10	Linear Search	Index=4	arr[4] == 12?	No, move to next	[3, 5, 7, 9, 11]
11	Linear Search end	Index=5	Index >= n?	Target not found	[3, 5, 7, 9, 11]
12	Binary Search start	low=0, high=4	Calculate mid=2	Check arr[2] == 12?	[3, 5, 7, 9, 11]
13	Binary Search	mid=2	arr[2] < 12?	Yes, low = mid+1 = 3	[3, 5, 7, 9, 11]
14	Binary Search	low=3, high=4	Calculate mid=3	Check arr[3] == 12?	[3, 5, 7, 9, 11]
15	Binary Search	mid=3	arr[3] < 12?	Yes, low = mid+1 = 4	[3, 5, 7, 9, 11]
16	Binary Search	low=4, high=4	Calculate mid=4	Check arr[4] == 12?	[3, 5, 7, 9, 11]
17	Binary Search	mid=4	arr[4] == 12?	No, arr[4] < 12? Yes, low = mid+1 = 5	[3, 5, 7, 9, 11]
18	Binary Search	low=5, high=4	low <= high?	No, target not found	[3, 5, 7, 9, 11]

💡 Linear search stops after checking all elements or finding target; binary search stops when low > high or target found.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 11	After Step 18
Linear Search index	0	2 (found target)	2	5 (end, not found)	5
Binary Search low	0	0	0	0	5
Binary Search high	4	4	4	4	4
Binary Search mid	2	2 (found target)	2	2	4

Key Moments - 3 Insights

Why does binary search calculate mid as (low + high) / 2 instead of just picking a random index?

Binary search splits the search range in half each time to reduce search space efficiently. The mid calculation (low + high) / 2 finds the middle index to check, as shown in execution_table steps 4, 12, 14, and 16.

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, so it can take up to n steps. Binary search cuts the search space in half each time, so it usually finds the target faster, as seen comparing steps 1-3 (linear) vs 4-5 (binary).

Why does binary search stop when low > high?

When low becomes greater than high, it means the target is not in the array because the search space is empty. This is shown in execution_table step 18 where low=5 and high=4, so binary search ends without finding the target.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 14 during binary search?

A 4

B 2

C 3

D 1

💡 Hint

Check the 'Index Checked / Mid' column at step 14 in execution_table.

At which step does linear search conclude the target 12 is not found?

A Step 10

B Step 11

C Step 9

D Step 12

💡 Hint

Look for the step where linear search index reaches array size and stops.

If the target was 5, how many steps would linear search take to find it according to the execution_table pattern?

A 2

B 1

C 3

D 4

💡 Hint

Look at how many steps linear search took to find 7 at index 2, then consider 5 is at index 1.

Concept Snapshot

Linear Search:
- Check each element from start to end
- Time: O(n) worst case

Binary Search:
- Requires sorted array
- Check middle element, reduce search space
- Time: O(log n) worst case

Binary search is faster but needs sorted data.

Full Transcript

This visual compares linear search and binary search by tracing their steps to find a target in an array. Linear search checks each element one by one until it finds the target or reaches the end. Binary search works only on sorted arrays and repeatedly splits the search range in half by checking the middle element. The execution table shows how linear search takes more steps when the target is near the end or not present, while binary search finds the target faster or concludes absence quicker by adjusting low and high pointers. Key moments clarify why binary search calculates the middle index and why it stops when the search space is empty. The quizzes test understanding of mid calculation, stopping conditions, and step counts. The snapshot summarizes the main differences and time complexities.

Practice

1. Which search algorithm generally performs faster on a sorted array 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 search space in half each step, while Linear Search checks elements one by one.

2. Step 2: Compare performance on large sorted arrays

   Binary Search takes about log2(1,000,000) ≈ 20 steps, Linear Search may take up to 1,000,000 steps.

3. Final Answer:

   Binary Search -> Option A

4. Quick Check:

   Binary Search is faster on sorted large arrays [OK]

Hint: Binary Search halves search space, so faster on sorted data [OK]

Common Mistakes:

• Thinking Linear Search is faster because it is simpler
• Ignoring that array must be sorted for Binary Search
• Assuming both have same speed regardless of data size

2. Which of the following is the correct syntax to start a binary search on a sorted array arr of size n in C++?

easy

A. int low = 0, high = n - 1;

B. int low = 1, high = n;

C. int low = 0, high = n;

D. int low = 1, high = n - 1;

Solution

1. Step 1: Understand array indexing in C++

   Arrays start at index 0, so first element is at 0 and last at n-1.

2. Step 2: Set binary search boundaries correctly

   Low should be 0 and high should be n-1 to cover entire array.

3. Final Answer:

   int low = 0, high = n - 1; -> Option A

4. Quick Check:

   Array indices start at 0, so low=0 and high=n-1 [OK]

Hint: Array indexing starts at 0, so high = n - 1 [OK]

Common Mistakes:

• Starting low at 1 instead of 0
• Setting high to n instead of n-1
• Confusing 1-based indexing with 0-based

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

int arr[] = {2, 4, 6, 8, 10};
int n = 5;
int target = 6;
int low = 0, high = n - 1;
int steps = 0;
while (low <= high) {
    steps++;
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        break;
    } else if (arr[mid] < target) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
std::cout << steps << std::endl;

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace first iteration

   low=0, high=4, mid=2, arr[2]=6 equals target, steps=1, loop breaks immediately.

2. Step 2: Confirm steps count

   Steps incremented once before break, so output is 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Target found at first mid check, steps = 1 [OK]

Hint: Binary Search finds target quickly, count mid checks [OK]

Common Mistakes:

• Counting steps after break incorrectly
• Miscomputing mid index
• Assuming more iterations needed when target is mid

4. Identify the error in the following linear search code snippet and choose the correct fix:

int linearSearch(int arr[], int n, int target) {
    for (int i = 1; i <= n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

medium

A. Change return i to return i + 1

B. Change loop to for (int i = 0; i < n; i++)

C. Change loop to for (int i = 1; i < n; i++)

D. No error, code is correct

Solution

1. Step 1: Analyze array indexing

   Arrays in C++ start at 0, but loop starts at 1 and goes to n, causing out-of-bounds access.

2. Step 2: Fix loop boundaries

   Loop should start at 0 and run while i < n to cover all elements safely.

3. Final Answer:

   Change loop to for (int i = 0; i < n; i++) -> Option B

4. Quick Check:

   Array indexing starts at 0, loop must reflect that [OK]

Hint: Array indices start at 0, loop from 0 to n-1 [OK]

Common Mistakes:

• Starting loop at 1 causing skip of first element
• Using <= n causing out-of-bounds access
• Assuming array indexing starts at 1

5. You have a sorted array of 1,000 elements and want to find if the number 500 exists. Which search method is more cost-effective considering average case and why?

hard

A. Linear Search, because it uses less memory

B. Linear Search, because it checks elements sequentially

C. Binary Search, because it reduces search space exponentially

D. Binary Search, but only if the array is unsorted

Solution

1. Step 1: Consider array sortedness and search methods

   Binary Search requires sorted array and halves search space each step; Linear Search checks each element one by one.

2. Step 2: Compare average case cost

   Binary Search takes about log2(1000) ≈ 10 steps; Linear Search takes on average 500 steps.

3. Final Answer:

   Binary Search, because it reduces search space exponentially -> Option C

4. Quick Check:

   Sorted array + binary search = faster average search [OK]

Hint: Use Binary Search on sorted arrays for faster average search [OK]

Common Mistakes:

• Choosing Linear Search for sorted arrays
• Confusing memory use with search speed
• Thinking Binary Search works on unsorted arrays