Why Binary Search and What Sorted Order Gives You in DSA Go - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

What is the output of this Go code that performs binary search on a sorted array to find the index of number 7?

DSA Go

package main
import "fmt"
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}
func main() {
    arr := []int{1, 3, 5, 7, 9, 11}
    fmt.Println(binarySearch(arr, 7))
}

A 2

B 3

C -1

D 4

💡 Hint

Remember that array indexing starts at 0 and the array is sorted.

The number 7 is at index 3 in the sorted array [1,3,5,7,9,11]. Binary search finds it and returns 3.

🧠 Conceptual

intermediate

Why Must the Array Be Sorted for Binary Search?

Why is it necessary for the array to be sorted before applying binary search?

A Because binary search compares the target with the middle element to decide which half to search next, which only works if the array is sorted.

B Because binary search only works on arrays with unique elements.

C Because binary search can only find the first element in any array.

D Because binary search requires the array to be sorted in descending order only.

💡 Hint

Think about how binary search decides which half to discard.

Binary search relies on the order of elements to eliminate half of the search space each time. Without sorting, it cannot decide which half to discard.

❓ Predict Output

advanced

Result of Binary Search on Unsorted Array

What is the output of this Go code that performs binary search on an unsorted array to find the index of number 7?

DSA Go

package main
import "fmt"
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}
func main() {
    arr := []int{9, 1, 5, 3, 11, 7}
    fmt.Println(binarySearch(arr, 7))
}

A -1

B 2

C 3

D 0

💡 Hint

Binary search assumes sorted order; what happens if the array is not sorted?

The array is not sorted, so binary search cannot reliably find the target. It returns -1 indicating not found.

🔧 Debug

advanced

Identify the Bug in Binary Search Implementation

What is the bug in this binary search code that causes it to fail on some inputs?

DSA Go

package main
import "fmt"
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left < right {
        mid := (left + right) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return -1
}
func main() {
    arr := []int{1, 3, 5, 7, 9}
    fmt.Println(binarySearch(arr, 9))
}

A The mid calculation should be left + (right-left)/2 to avoid overflow.

B The loop condition should be left <= right, not left < right.

C The initial right should be len(arr)-1, not len(arr).

D The function should return left instead of -1 when not found.

💡 Hint

Check the range of indices used for right boundary.

Using right = len(arr) causes mid to sometimes be out of range, leading to runtime errors or incorrect results.

🧠 Conceptual

expert

Why Binary Search is Faster Than Linear Search on Large Sorted Data

Why does binary search perform faster than linear search on large sorted arrays?

A Because binary search uses recursion and recursion is always faster than loops.

B Because linear search requires the array to be sorted, which adds overhead.

C Because binary search only works on arrays with fewer elements.

D Because binary search reduces the search space by half each step, leading to logarithmic time complexity, while linear search checks each element one by one.

💡 Hint

Think about how many elements each algorithm checks as the array size grows.

Binary search halves the search space each step, so it takes fewer steps as the array grows, unlike linear search which checks every element.