Binary Search vs Linear Search Real Cost Difference in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linear Search on Sorted Array

What is the output of the following Go code that performs a linear search for the value 7 in a sorted array?

DSA Go

package main
import "fmt"
func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}
func main() {
    arr := []int{1, 3, 5, 7, 9, 11}
    index := linearSearch(arr, 7)
    fmt.Println(index)
}

A 4

B 2

C -1

D 3

💡 Hint

Linear search returns the index of the first matching element.

The value 7 is at index 3 in the array. Linear search checks each element from the start until it finds 7.

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

What is the output of the following Go code that performs a binary search for the value 7 in a sorted array?

DSA Go

package main
import "fmt"
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
}
func main() {
    arr := []int{1, 3, 5, 7, 9, 11}
    index := binarySearch(arr, 7)
    fmt.Println(index)
}

A 3

B 2

C -1

D 4

💡 Hint

Binary search divides the array and finds the target efficiently.

The value 7 is at index 3. Binary search finds it by checking the middle element and narrowing the search.

🧠 Conceptual

advanced

Time Complexity Comparison

Which statement correctly compares the average time complexity of linear search and binary search on a sorted array of size n?

A Linear search is O(n), binary search is O(log n)

B Linear search is O(log n), binary search is O(n)

C Both linear and binary search are O(n)

D Both linear and binary search are O(log n)

💡 Hint

Binary search cuts the search space in half each step.

Linear search checks each element one by one, so it takes O(n). Binary search divides the search space by two each time, so it takes O(log n).

🚀 Application

advanced

Choosing Search Method for Unsorted Data

You have a large unsorted list of numbers and need to find if a target number exists. Which search method is best and why?

A Binary search, because it is always faster

B Neither, use a hash table instead

C Linear search, because binary search requires sorted data

D Binary search after sorting the list every time you search

💡 Hint

Binary search needs sorted data to work correctly.

Binary search only works on sorted data. Sorting every time is expensive. Linear search works on unsorted data directly.

🔧 Debug

expert

Bug in Binary Search Implementation

What error does the following Go code produce when searching for 12 in the array? Identify the output or error.

DSA Go

package main
import "fmt"
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
}
func main() {
    arr := []int{1, 3, 5, 7, 9, 11}
    index := binarySearch(arr, 12)
    fmt.Println(index)
}

A -1

B runtime error: index out of range

C 3

D 0

💡 Hint

Check the initial value of high and array indexing.

The variable high is set to len(arr), which is out of valid index range (max index is len(arr)-1). This causes an index out of range runtime error when mid equals len(arr).