Binary Search Iterative Approach in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search for Existing Element

What is the output of the following Go code that performs an iterative binary search for the number 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-low)/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}
    fmt.Println(binarySearch(arr, 7))
}

A -1

B 2

C 3

D 4

💡 Hint

Remember that array indices start at 0 and the array is sorted.

The number 7 is at index 3 in the array [1, 3, 5, 7, 9, 11]. The binary search returns the index where the target is found.

❓ Predict Output

intermediate

Output of Binary Search for Non-Existing Element

What is the output of the following Go code that performs an iterative binary search for the number 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-low)/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{2, 4, 6, 8, 10, 12}
    fmt.Println(binarySearch(arr, 7))
}

A 4

B 3

C 2

D -1

💡 Hint

Check if the target exists in the array and note its index.

The number 7 is not present in the array [2, 4, 6, 8, 10, 12]. The binary search returns -1 when the target is not found.

❓ Predict Output

advanced

Output of Binary Search with Duplicate Elements

What is the output of the following Go code that performs an iterative binary search for the number 5 in a sorted array with duplicates?

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-low)/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, 5, 5, 7, 9}
    fmt.Println(binarySearch(arr, 5))
}

A 2

B 3

C 4

D -1

💡 Hint

Binary search may return any index where the target is found.

The binary search returns index 3 where 5 is found (among indices 2,3,4). It may not always return the first or last duplicate but a valid index.

🧠 Conceptual

advanced

Why Use Iterative Binary Search Instead of Recursive?

Which of the following is the main advantage of using an iterative approach for binary search over a recursive one?

A Iterative approach uses less memory by avoiding function call stack overhead.

B Iterative approach is easier to write and understand than recursive.

C Iterative approach can handle unsorted arrays.

D Iterative approach always finds the first occurrence of duplicates.

💡 Hint

Think about memory usage and function calls.

Iterative binary search avoids the overhead of recursive calls, saving memory and reducing risk of stack overflow.

🔧 Debug

expert

Identify the Bug in Binary Search Implementation

What error will the following Go code produce when running binary search on the array [1, 2, 3, 4, 5] searching for 6?

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-low)/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, 2, 3, 4, 5}
    fmt.Println(binarySearch(arr, 6))
}

A runtime error: index out of range

B returns 2 (correct index)

C returns -1 (not found)

D compilation error

💡 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). Accessing arr[mid] can cause index out of range error.