Binary Search vs Linear Search Real Cost Difference in DSA Go - Build Both Approaches

Binary Search vs Linear Search Real Cost Difference

📖 Scenario: You are working in a library system that keeps a sorted list of book IDs. You want to find if a specific book ID is available. You will compare two ways to search: linear search (checking one by one) and binary search (dividing the list to find faster).

🎯 Goal: Build a Go program that creates a sorted list of book IDs, sets a target book ID to find, implements both linear search and binary search to find the target, and prints the results showing which method found the book and at what index.

📋 What You'll Learn

Create a sorted slice of integers called bookIDs with these exact values: 101, 203, 305, 407, 509, 611, 713, 815, 917, 1020

Create an integer variable called targetID and set it to 713

Write a function called linearSearch that takes bookIDs and targetID and returns the index of targetID or -1 if not found

Write a function called binarySearch that takes bookIDs and targetID and returns the index of targetID or -1 if not found

Print the results of both searches with clear messages

💡 Why This Matters

🌍 Real World

Searching sorted lists quickly is important in many systems like libraries, databases, and online stores to find items fast.

💼 Career

Understanding linear and binary search helps in optimizing search operations and improving software performance in real-world applications.

1

Create the sorted list of book IDs

Create a slice of integers called bookIDs with these exact values: 101, 203, 305, 407, 509, 611, 713, 815, 917, 1020

DSA Go

# Create the sorted slice bookIDs with the given values
# Your code here

Hint

Use bookIDs := []int{...} with the exact numbers inside the braces.

2

Set the target book ID to find

Create an integer variable called targetID and set it to 713

DSA Go

package main

func main() {
    bookIDs := []int{101, 203, 305, 407, 509, 611, 713, 815, 917, 1020}
    // Create targetID variable and set to 713
    // Your code here
}

Hint

Use targetID := 713 inside the main function.

3

Write linearSearch and binarySearch functions

Write a function called linearSearch that takes bookIDs and targetID and returns the index of targetID or -1 if not found. Also write a function called binarySearch that takes bookIDs and targetID and returns the index of targetID or -1 if not found.

DSA Go

package main

func linearSearch(bookIDs []int, targetID int) int {
    // Your code here
}

func binarySearch(bookIDs []int, targetID int) int {
    // Your code here
}

func main() {
    bookIDs := []int{101, 203, 305, 407, 509, 611, 713, 815, 917, 1020}
    targetID := 713
}

Hint

Use a for loop with range for linear search. For binary search, use low, high, and mid indexes to divide the list.

4

Print the search results

Print the results of both searches using fmt.Println. Print exactly these two lines: "Linear Search: Found at index" followed by the linear search result, and "Binary Search: Found at index" followed by the binary search result.

DSA Go

package main

import "fmt"

func linearSearch(bookIDs []int, targetID int) int {
    for i, id := range bookIDs {
        if id == targetID {
            return i
        }
    }
    return -1
}

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

func main() {
    bookIDs := []int{101, 203, 305, 407, 509, 611, 713, 815, 917, 1020}
    targetID := 713
    // Print linear search result
    // Print binary search result
    // Your code here
}

Hint

Call both search functions with bookIDs and targetID. Store results in variables and print with fmt.Println exactly as shown.

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