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.

Practice

1. What is the main idea behind the binary search recursive approach on a sorted array?

easy

A. Sort the array first and then search linearly

B. Divide the array into halves and search recursively in the half where the target may exist

C. Search each element one by one from start to end

D. Use a queue to store elements and search iteratively

Solution

1. Step 1: Understand binary search logic

   Binary search works by dividing the sorted array into two halves and deciding which half to search next based on comparison with the middle element.

2. Step 2: Apply recursion in binary search

   The recursive approach calls the same function on the half where the target might be, reducing the search space each time.

3. Final Answer:

   Divide the array into halves and search recursively in the half where the target may exist -> Option B

4. Quick Check:

   Binary search = divide and conquer [OK]

Hint: Remember: binary search splits array and searches half recursively [OK]

Common Mistakes:

• Trying to search linearly instead of dividing
• Not using recursion properly
• Ignoring that array must be sorted

2. Which of the following is the correct function signature for a recursive binary search in Go?

easy

A. func binarySearch(arr []int, target int, mid int) int

B. func binarySearch(arr []int, target int) int

C. func binarySearch(arr []int, target int, low int, high int) int

D. func binarySearch(arr []int) int

Solution

1. Step 1: Identify parameters needed for recursion

   Recursive binary search needs the array, target, and the current low and high indices to know the search range.

2. Step 2: Check function signatures

   func binarySearch(arr []int, target int, low int, high int) int includes low and high indices, which are essential for recursion. Others miss these or have incorrect parameters.

3. Final Answer:

   func binarySearch(arr []int, target int, low int, high int) int -> Option C

4. Quick Check:

   Parameters include low and high indices [OK]

Hint: Recursive binary search needs low and high index parameters [OK]

Common Mistakes:

• Omitting low and high indices in parameters
• Adding unnecessary parameters like mid
• Using wrong return types

3. What will be the output of the following Go code snippet?

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

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

medium

A. 0

B. 3

C. -1

D. 2

Solution

1. Step 1: Trace the recursive calls for target 6

   Initial call: low=0, high=4, mid=2, arr[2]=6 equals target, so return 2 immediately.

2. Step 2: Confirm output

   Since target found at index 2, output is 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Target 6 found at index 2 [OK]

Hint: Check mid index value first to find target quickly [OK]

Common Mistakes:

• Confusing index with value
• Not updating low and high correctly
• Returning wrong index or -1 incorrectly

4. Identify the error in the following recursive binary search function and select the fix:

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

medium

A. Change condition to if low > high instead of low >= high

B. Change mid calculation to mid := (low + high + 1) / 2

C. Return 0 instead of -1 when not found

D. Remove else if and use only if statements

Solution

1. Step 1: Analyze base case condition

   The base case should stop recursion when low is greater than high, meaning no elements left to search. Using low >= high skips searching when low equals high, missing that element.

2. Step 2: Correct the condition

   Changing to low > high allows searching the last element when low equals high.

3. Final Answer:

   Change condition to if low > high instead of low >= high -> Option A

4. Quick Check:

   Base case must allow low == high search [OK]

Hint: Base case should be low > high, not low >= high [OK]

Common Mistakes:

• Stopping recursion too early with wrong base case
• Incorrect mid calculation causing infinite recursion
• Returning wrong default value when not found

5. Given a sorted array with possible duplicate elements, how can you modify the recursive binary search to find the first occurrence of a target value?

hard

A. When target found, check if previous element is same; if yes, search left half recursively

B. Return the first found index immediately without further checks

C. Search only the right half recursively after finding target

D. Use linear search after binary search to find first occurrence

Solution

1. Step 1: Understand duplicates in binary search

   Standard binary search returns any occurrence of target. To find first occurrence, we must check if earlier elements are also equal.

2. Step 2: Modify recursion to check left side

   When target found at mid, check if mid is first index or previous element is different. If previous element is same, recursively search left half to find earlier occurrence.

3. Final Answer:

   When target found, check if previous element is same; if yes, search left half recursively -> Option A

4. Quick Check:

   Check left side for first occurrence [OK]

Hint: On finding target, move left if previous equals target [OK]

Common Mistakes:

• Returning first found index without checking duplicates
• Searching right half instead of left for first occurrence
• Using linear search unnecessarily