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

Concept Flow - Binary Search vs Linear Search Real Cost Difference

Start at index 0

↓

Check element == target?

No→Move to next index

↓

End: Not found

↓

Return index

↓

Start with low=0, high=n-1

↓

Calculate mid = (low+high)/2

↓

Check element at mid == target?

↓

Return

↓

Repeat until low > high

↓

Return not found

Linear search checks each element one by one from start to end. Binary search divides the search range in half each step, quickly narrowing down the target location.

Execution Sample

DSA Rust

let arr = [2, 4, 6, 8, 10];
let target = 8;
// Linear Search
for i in 0..arr.len() {
    if arr[i] == target {
        return Some(i);
    }
}
// Binary Search
let mut low = 0;
let mut high = arr.len() - 1;
while low <= high {
    let mid = (low + high) / 2;
    if arr[mid] == target {
        return Some(mid);
    } else if arr[mid] < target {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
return None;

This code searches for target 8 in a sorted array using linear and binary search, showing how many steps each takes.

Execution Table

Step	Search Type	Operation	Index Checked	Comparison Result	Pointer Changes	Visual State
1	Linear	Check element	0	2 != 8	i=0->1	[2, 4, 6, 8, 10]
2	Linear	Check element	1	4 != 8	i=1->2	[2, 4, 6, 8, 10]
3	Linear	Check element	2	6 != 8	i=2->3	[2, 4, 6, 8, 10]
4	Linear	Check element	3	8 == 8	i=3	[2, 4, 6, 8, 10]
5	Binary	Initialize pointers	-	-	low=0, high=4	[2, 4, 6, 8, 10]
6	Binary	Calculate mid	-	-	mid=2	[2, 4, 6, 8, 10]
7	Binary	Compare mid element	2	6 < 8	low=3	[2, 4, 6, 8, 10]
8	Binary	Calculate mid	-	-	mid= (3+4)/2=3	[2, 4, 6, 8, 10]
9	Binary	Compare mid element	3	8 == 8	Found target	[2, 4, 6, 8, 10]

💡 Linear search stops at step 4 when target found; binary search stops at step 9 when target found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9
i (Linear)	0	1	2	3	3	-	-	-	-	-
low (Binary)	-	-	-	-	-	0	0	3	3	3
high (Binary)	-	-	-	-	-	4	4	4	4	4
mid (Binary)	-	-	-	-	-	-	2	2	3	3

Key Moments - 3 Insights

Why does linear search check every element until it finds the target?

Because linear search does not assume any order, it must check each element one by one until it finds the target or reaches the end, as shown in steps 1 to 4 in execution_table.

Why does binary search update low or high pointers instead of checking every element?

Binary search uses the sorted order to eliminate half the search space each time by updating low or high pointers, as seen in steps 7 and 8 where low changes from 0 to 3, narrowing the search.

Why does binary search calculate mid as (low + high) / 2?

Calculating mid finds the middle index of the current search range, allowing binary search to split the array and decide which half to search next, shown in steps 6 and 8.

Visual Quiz - 3 Questions

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

A Step 2

B Step 6

C Step 4

D Step 9

💡 Hint

Check the 'Comparison Result' column for linear search rows.

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

A Step 7

B Step 6

C Step 5

D Step 8

💡 Hint

Look at the 'Pointer Changes' column for binary search steps.

If the target was 5 (not in array), how would binary search's final step change?

A It would find target at mid index

B It would update low and high until low > high and return not found

C It would check every element like linear search

D It would stop immediately at step 5

💡 Hint

Binary search continues until low > high if target not found, as shown in the exit_note.

Concept Snapshot

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

Binary Search:
- Requires sorted array
- Check middle element, narrow search range
- Time: O(log n)

Binary search is faster on large sorted data due to halving search space each step.

Full Transcript

This visual compares linear and binary search costs by tracing their steps searching for target 8 in array [2,4,6,8,10]. Linear search checks elements one by one until it finds 8 at index 3 in 4 steps. Binary search starts with low=0 and high=4, calculates mid=2, finds 6 less than 8, updates low to 3, recalculates mid=3, and finds 8 at step 9. Variables i, low, high, mid change accordingly. Key moments clarify why linear search checks all elements and binary search narrows search space by updating pointers. Quizzes test understanding of when target is found and pointer updates. Summary highlights linear search's simplicity and binary search's efficiency on sorted data.

Practice

1. Which search method is generally faster on a sorted list of 1,000,000 elements?

easy

A. Depends on the element's position only

B. Linear Search

C. Both are equally fast

D. Binary Search

Solution

1. Step 1: Understand search methods on sorted lists

   Binary Search divides the list repeatedly, reducing search space quickly. Linear Search checks elements one by one.

2. Step 2: Compare time complexity for large lists

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

3. Final Answer:

   Binary Search -> Option D

4. Quick Check:

   Binary Search faster on sorted large lists [OK]

Hint: Binary Search halves search space each step [OK]

Common Mistakes:

• Thinking Linear Search is faster for sorted lists
• Ignoring list size impact
• Confusing sorted vs unsorted list performance

2. Which Rust code snippet correctly implements a linear search for a value in a slice?

easy

A. fn linear_search(arr: &[i32], target: i32) -> Option<usize> { let mut i = 0; while i < arr.len() { if arr[i] == target { return Some(i); } i += 1; } None }

B. fn linear_search(arr: &[i32], target: i32) -> Option<usize> { for i in 0..arr.len()-1 { if arr[i] == target { return Some(i); } } None }

C. fn linear_search(arr: &[i32], target: i32) -> usize { for i in 0..arr.len() { if arr[i] == target { return i; } } 0 }

D. fn linear_search(arr: &[i32], target: i32) -> Option<usize> { for i in 1..arr.len() { if arr[i] == target { return Some(i); } } None }

Solution

1. Step 1: Check function signature and return type

   Correct implementations should return Option<usize>, idiomatic for search functions. Returning plain usize with 0 on not found is ambiguous since index 0 is valid.

2. Step 2: Verify loop correctness and indexing

   The for loop from 0 to arr.len()-1 misses the last element. The while loop with mutable i from 0 while i < arr.len() covers all indices correctly. The for loop from 1 skips index 0.

3. Final Answer:

   While loop version -> Option A

4. Quick Check:

   Correct linear search loop and return [OK]

Hint: Check loop covers all indices and returns Option properly [OK]

Common Mistakes:

• Skipping first element in loop
• Returning ambiguous index instead of Option
• Incorrect loop bounds

3. What is the output of this Rust code using binary search on a sorted array?

let arr = [2, 4, 6, 8, 10];
let target = 6;
let result = arr.binary_search(&target);
println!("{:?}", result);

medium

A. Err(2)

B. Ok(2)

C. Ok(3)

D. Err(3)

Solution

1. Step 1: Understand binary_search return type

   Rust's binary_search returns Ok(index) if found, Err(insert_pos) if not found.

2. Step 2: Find target index in array

   Array is [2,4,6,8,10], target 6 is at index 2 (0-based).

3. Final Answer:

   Ok(2) -> Option B

4. Quick Check:

   binary_search returns Ok(index) when found [OK]

Hint: binary_search returns Ok(index) if found [OK]

Common Mistakes:

• Confusing Ok and Err results
• Miscounting zero-based index
• Assuming Err means found

4. Identify the bug in this Rust binary search implementation and select the fix:

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len();
    while low <= high {
        let mid = (low + high) / 2;
        if arr[mid] == target {
            return Some(mid);
        } else if arr[mid] < target {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    None
}

medium

A. Change high initialization to arr.len() - 1

B. Change while condition to low > high

C. Change mid calculation to low + (high - low) / 2

D. No bug, code is correct

Solution

1. Step 1: Analyze high variable initialization

   High is set to arr.len(), which is out of bounds since valid indices are 0 to arr.len()-1.

2. Step 2: Fix high initialization

   Set high to arr.len() - 1 to avoid index out of bounds error when accessing arr[mid].

3. Final Answer:

   Change high initialization to arr.len() - 1 -> Option A

4. Quick Check:

   High must be last valid index [OK]

Hint: High index must be last valid array index [OK]

Common Mistakes:

• Using arr.len() as high causes out of bounds
• Changing while condition incorrectly
• Ignoring mid calculation overflow

5. You have a sorted list of 10,000 elements and want to find if a value exists. Which approach minimizes average search steps considering the cost of comparisons and index calculations?

Assume:
- Each comparison costs 1 unit
- Each index calculation (like mid) costs 2 units
- Linear search does only comparisons
- Binary search does comparisons + index calculations per step

hard

A. Linear search is cheaper because it avoids index calculations

B. Both have equal cost on average

C. Binary search is cheaper because it reduces comparisons drastically despite index costs

D. Linear search is cheaper only if the element is near the start

Solution

1. Step 1: Calculate linear search average cost

   Linear search average steps = n/2 = 5000 comparisons, cost = 5000 * 1 = 5000 units.

2. Step 2: Calculate binary search average cost

   Binary search steps = log2(10000) ≈ 14 steps. Each step costs 1 (comparison) + 2 (index calc) = 3 units. Total = 14 * 3 = 42 units.

3. Step 3: Compare costs

   42 units (binary) << 5000 units (linear), so binary search is cheaper on average.

4. Final Answer:

   Binary search is cheaper because it reduces comparisons drastically despite index costs -> Option C

5. Quick Check:

   Binary search cost << Linear search cost [OK]

Hint: Binary search steps grow logarithmically, beating linear cost [OK]

Common Mistakes:

• Ignoring index calculation cost
• Assuming linear search always cheaper
• Misestimating average steps