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

Concept Flow - Binary Search vs Linear Search Real Cost Difference

Start Search

↓

Is list sorted?

|Yes↓

Binary Search

↓

Set low=0, high=n-1

↓

Calculate mid=(low+high)/2

↓

Compare target with mid element

↓

Found, return index

↓

high=mid-1

↓

low=mid+1

↓

Repeat until low > high

↓

Not found, return -1

↓

If list not sorted

↓

Linear Search

↓

Start from index 0

↓

Compare each element with target

↓

Found, return index

↓

Move to next index

↓

Repeat until end of list

↓

Not found, return -1

The flow shows how binary search works on a sorted list by dividing the search space, while linear search checks each element one by one when the list is unsorted.

Execution Sample

DSA Go

func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        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 checking each element and binary search dividing the list to find the target.

Execution Table

Step	Operation	Search Type	Index Checked	Comparison Result	Pointer Changes	Visual State
1	Start linear search	Linear	-	-	-	[3, 5, 7, 9, 11]
2	Check index 0	Linear	0	3 != 7	-	[3, 5, 7, 9, 11]
3	Check index 1	Linear	1	5 != 7	-	[3, 5, 7, 9, 11]
4	Check index 2	Linear	2	7 == 7	-	[3, 5, 7, 9, 11]
5	Return index 2	Linear	-	-	-	[3, 5, 7, 9, 11]
6	Start binary search	Binary	-	-	low=0, high=4	[3, 5, 7, 9, 11]
7	Calculate mid	Binary	2	arr[2] == 7	-	[3, 5, 7, 9, 11]
8	Return index 2	Binary	-	-	-	[3, 5, 7, 9, 11]
9	Start linear search for 12	Linear	-	-	-	[3, 5, 7, 9, 11]
10	Check index 0	Linear	0	3 != 12	-	[3, 5, 7, 9, 11]
11	Check index 1	Linear	1	5 != 12	-	[3, 5, 7, 9, 11]
12	Check index 2	Linear	2	7 != 12	-	[3, 5, 7, 9, 11]
13	Check index 3	Linear	3	9 != 12	-	[3, 5, 7, 9, 11]
14	Check index 4	Linear	4	11 != 12	-	[3, 5, 7, 9, 11]
15	Return -1 (not found)	Linear	-	-	-	[3, 5, 7, 9, 11]
16	Start binary search for 12	Binary	-	-	low=0, high=4	[3, 5, 7, 9, 11]
17	Calculate mid	Binary	2	arr[2] == 7 < 12	low=3	[3, 5, 7, 9, 11]
18	Calculate mid	Binary	3	arr[3] == 9 < 12	low=4	[3, 5, 7, 9, 11]
19	Calculate mid	Binary	4	arr[4] == 11 < 12	low=5	[3, 5, 7, 9, 11]
20	low > high, return -1	Binary	-	-	-	[3, 5, 7, 9, 11]

💡 Search ends when target is found or all elements checked (linear) or low > high (binary).

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 7	After Step 17	After Step 18	After Step 19	Final
i (linear index)	-	0	1	2	-	-	-	-	-	-
low (binary)	-	-	-	-	0	0	3	4	5	5
high (binary)	-	-	-	-	4	4	4	4	4	4
mid (binary)	-	-	-	-	-	2	2	3	4	-
target	7	7	7	7	7	7	12	12	12	12
found index	-	-	2	2	-	2	-	-	-	-1

Key Moments - 3 Insights

Why does binary search require the list to be sorted?

Binary search divides the list based on comparisons; if the list is not sorted, the logic to discard half the list fails. This is shown in steps 6-20 where low and high pointers move based on sorted order.

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

Linear search has no assumption about order, so it must check each element one by one as shown in steps 2-5 and 9-15 until it finds the target or finishes the list.

What happens when the target is not in the list in binary search?

Binary search moves low and high pointers until low > high, meaning the target is not found, as shown in steps 16-20 where low increments beyond high and returns -1.

Visual Quiz - 3 Questions

Look at the execution table, at which step does binary search find the target 7?

A Step 18

B Step 4

C Step 7

D Step 15

💡 Hint

Check the 'Comparison Result' column for 'arr[2] == 7' in the binary search rows.

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

A Step 14

B Step 15

C Step 20

D Step 19

💡 Hint

Look for the linear search step with 'Return -1 (not found)' in the 'Operation' column.

If the array was unsorted, which search method would still guarantee finding the target?

A Linear Search

B Binary Search

C Both

D Neither

💡 Hint

Refer to the concept flow where linear search works on unsorted lists but binary search requires sorted lists.

Concept Snapshot

Binary Search vs Linear Search

- Linear Search checks each element one by one.
- Binary Search divides sorted list to find target faster.
- Binary Search needs sorted data; Linear does not.
- Binary Search is O(log n), Linear is O(n).
- Use Binary Search for sorted arrays for efficiency.

Full Transcript

This lesson compares binary search and linear search by showing how each checks elements to find a target value. Linear search checks elements one by one from start to end, suitable for unsorted lists but slower for large data. Binary search works only on sorted lists by repeatedly dividing the search range, quickly narrowing down where the target could be. The execution table traces both searches finding the target 7 and failing to find 12, showing pointer movements and comparisons. Key moments clarify why binary search requires sorted data and how linear search always checks all elements. The visual quiz tests understanding of steps where targets are found or not found and which search works on unsorted data. The snapshot summarizes the main differences and when to use each search method.

Practice

1. Which search algorithm is generally faster for finding an element in a sorted list of 1,000,000 items?

easy

A. Neither works on sorted lists

B. Linear Search

C. Binary Search

D. Both are equally fast

Solution

1. Step 1: Understand the search algorithms

   Binary Search divides the list in half repeatedly, while Linear Search checks each item one by one.

2. Step 2: Compare efficiency on large sorted lists

   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 C

4. Quick Check:

   Binary Search is faster on sorted large lists [OK]

Hint: Binary Search halves list; Linear checks all items [OK]

Common Mistakes:

• Thinking Linear Search is faster on sorted lists
• Confusing sorted vs unsorted list requirements
• Assuming both have same speed

2. Which of the following is the correct Go syntax to perform a linear search on a slice named arr for a value target?

easy

A. for i, v := range arr { if v == target { return v } }

B. for i := 0; i < len(arr); i++ { if arr[i] == target { return i } }

C. for v in arr { if v == target { return i } }

D. while i < len(arr) { if arr[i] == target { return i } i++ }

Solution

1. Step 1: Review Go loop syntax for slices

   Go uses for loops with index and length or range loops; for v in arr { if v == target { return i } } uses invalid syntax, while i < len(arr) { if arr[i] == target { return i } i++ } uses while which Go does not have.

2. Step 2: Identify correct syntax for linear search

   for i := 0; i < len(arr); i++ { if arr[i] == target { return i } } uses a for loop with index and length, checking each element correctly.

3. Final Answer:

   for i := 0; i < len(arr); i++ { if arr[i] == target { return i } } -> Option B

4. Quick Check:

   Go uses for loops, not while [OK]

Hint: Go uses for loops, not while loops [OK]

Common Mistakes:

• Using Python or other language syntax in Go
• Using while loops which Go does not support
• Incorrect range loop syntax

3. Given the following Go code snippet, what will be printed?

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

func main() {
    arr := []int{3, 5, 7, 9, 11}
    index := linearSearch(arr, 7)
    fmt.Println(index)
}

medium

A. 2

B. 3

C. -1

D. 0

Solution

1. Step 1: Trace the linear search function

   The function checks each element in order: arr[0]=3, arr[1]=5, arr[2]=7 matches target 7.

2. Step 2: Return index of first match

   It returns index 2 immediately when it finds 7.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   7 is at index 2 in arr [OK]

Hint: Linear search returns first matching index [OK]

Common Mistakes:

• Confusing index with value
• Assuming zero-based index is one-based
• Returning -1 incorrectly

4. The following Go code attempts to perform binary search on a sorted slice but does not work correctly. What is the main bug?

func binarySearch(arr []int, target int) int {
    low := 0
    high := len(arr)
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

medium

A. low should start at 1 instead of 0

B. mid calculation should use float division

C. The loop condition should be low < high

D. high should be initialized to len(arr) - 1

Solution

1. Step 1: Check initialization of high index

   In Go, slice indices go from 0 to len(arr)-1, so high should be len(arr)-1, not len(arr).

2. Step 2: Understand impact on loop and mid calculation

   Using len(arr) causes out-of-range access when mid equals len(arr), causing runtime error.

3. Final Answer:

   high should be initialized to len(arr) - 1 -> Option D

4. Quick Check:

   Slice max index = len(arr)-1 [OK]

Hint: High index = length minus one for slices [OK]

Common Mistakes:

• Setting high to len(arr) causes out-of-range error
• Using float division for mid index
• Incorrect loop condition

5. You have a sorted slice of 1,000,000 integers and want to find if the number 123456 exists. You can use either linear or binary search. Considering real cost difference, which approach is best and why?

hard

A. Use binary search because it reduces comparisons drastically

B. Use linear search because it is simpler to implement

C. Use linear search because it uses less memory

D. Use binary search only if the slice is unsorted

Solution

1. Step 1: Analyze the data and search requirements

   The slice is sorted, so binary search can be applied efficiently.

2. Step 2: Compare real cost of linear vs binary search

   Linear search may check up to 1,000,000 elements; binary search checks about 20 comparisons, saving time.

3. Final Answer:

   Use binary search because it reduces comparisons drastically -> Option A

4. Quick Check:

   Binary search best for sorted large data [OK]

Hint: Binary search cuts steps to log2(n) [OK]

Common Mistakes:

• Choosing linear search for large sorted data
• Confusing memory use with search speed
• Thinking binary search needs unsorted data