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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search on Sorted Array

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

DSA Go

package main
import "fmt"

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

func main() {
    arr := []int{1, 3, 5, 7, 9, 11}
    result := binarySearch(arr, 0, len(arr)-1, 7)
    fmt.Println(result)
}

A 2

B -1

C 3

D 4

💡 Hint

Remember that array indices start at 0 and the function returns the index of the target if found.

The target 7 is at index 3 in the array. The recursive binary search finds it and returns 3.

❓ Predict Output

intermediate

Result of Recursive Binary Search When Target Not Present

What will be printed when searching for 8 in the sorted array using the recursive binary search function below?

DSA Go

package main
import "fmt"

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

func main() {
    arr := []int{2, 4, 6, 10, 12}
    result := binarySearch(arr, 0, len(arr)-1, 8)
    fmt.Println(result)
}

A -1

B 2

C 3

D 0

💡 Hint

If the target is not found, the function returns -1.

Since 8 is not in the array, the function returns -1 indicating the target is absent.

🔧 Debug

advanced

Identify the Error in Recursive Binary Search Implementation

What error will occur when running this recursive binary search code?

DSA Go

package main
import "fmt"

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

func main() {
    arr := []int{1, 2, 3, 4, 5}
    result := binarySearch(arr, 0, len(arr)-1, 3)
    fmt.Println(result)
}

A Infinite recursion causing stack overflow

B Index out of range runtime panic

C Compiles but prints 0 always

D Returns -1 even if target is present

💡 Hint

Check the base case condition carefully.

The base case uses 'low >= high' which causes the function to return -1 even when low == high and the target is at that index. It should be 'low > high'.

🧠 Conceptual

advanced

Understanding Recursive Binary Search Time Complexity

What is the time complexity of the recursive binary search algorithm on a sorted array of size n?

A O(log n)

B O(1)

C O(n log n)

D O(n)

💡 Hint

Each recursive call halves the search space.

Binary search divides the array in half each time, so it runs in logarithmic time O(log n).

🚀 Application

expert

Find the Index of First Occurrence Using Recursive Binary Search

Given a sorted array with duplicate elements, which recursive binary search modification will correctly find the first occurrence index of the target value 5? Consider the array: [1, 2, 5, 5, 5, 7, 9]

DSA Go

package main
import "fmt"

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

func main() {
    arr := []int{1, 2, 5, 5, 5, 7, 9}
    result := firstOccurrence(arr, 0, len(arr)-1, 5)
    fmt.Println(result)
}

A 4

B 2

C -1

D 3

💡 Hint

Check if the mid element is the first occurrence or if you need to search left.

The function finds the first index where 5 appears, which is index 2 in the array.