Binary Search Recursive Approach in DSA Go

Mental Model

Binary search splits a sorted list in half to find a target quickly by checking the middle element and searching only the half that could contain the target.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if you should look in the first half or the second half, repeating this until you find the word.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0   1   2   3   4    5    6
          ↑               ↑
       low=0           high=6
          ↑
       mid=3 (value=7)

Dry Run Walkthrough

Input: list: [1, 3, 5, 7, 9, 11, 13], target: 9

Goal: Find the index of target 9 using recursive binary search

Step 1: Calculate mid index between low=0 and high=6; mid=3, value=7

[1, 3, 5, [7], 9, 11, 13] low=0 high=6 mid=3

Why: Check middle value to decide which half to search next

Step 2: Target 9 is greater than mid value 7, search right half: low=4, high=6

[1, 3, 5, 7, [9], 11, 13] low=4 high=6

Why: Target must be in the right half because 9 > 7

Step 3: Calculate mid index between low=4 and high=6; mid=5, value=11

[1, 3, 5, 7, 9, [11], 13] low=4 high=6 mid=5

Why: Check middle value of the new subarray

Step 4: Target 9 is less than mid value 11, search left half: low=4, high=4

[1, 3, 5, 7, [9], 11, 13] low=4 high=4

Why: Target must be in the left half because 9 < 11

Step 5: Calculate mid index between low=4 and high=4; mid=4, value=9

[1, 3, 5, 7, [9], 11, 13] low=4 high=4 mid=4

Why: Check the only element left

Step 6: Found target 9 at index 4, return index

[1, 3, 5, 7, [9], 11, 13]

Why: Target matches mid value, search ends

Result:

Final state: [1, 3, 5, 7, [9], 11, 13] Target found at index 4

Annotated Code

DSA Go

package main

import "fmt"

func binarySearchRecursive(arr []int, target int, low int, high int) int {
    if low > high {
        return -1 // target not found
    }
    mid := low + (high-low)/2
    if arr[mid] == target {
        return mid // target found
    } else if arr[mid] > target {
        return binarySearchRecursive(arr, target, low, mid-1) // search left half
    } else {
        return binarySearchRecursive(arr, target, mid+1, high) // search right half
    }
}

func main() {
    arr := []int{1, 3, 5, 7, 9, 11, 13}
    target := 9
    index := binarySearchRecursive(arr, target, 0, len(arr)-1)
    if index != -1 {
        fmt.Printf("Target %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Target %d not found\n", target)
    }
}

if low > high {

stop recursion if search range is invalid (target not found)

mid := low + (high-low)/2

calculate middle index to split search range

if arr[mid] == target {

check if middle element is the target

return binarySearchRecursive(arr, target, low, mid-1)

search left half if target is smaller than mid value

return binarySearchRecursive(arr, target, mid+1, high)

search right half if target is greater than mid value

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each recursive call halves the search range

Space: O(log n) due to recursive call stack depth proportional to log n

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted arrays by reducing search space quickly

Edge Cases

empty array

function returns -1 immediately as low > high

DSA Go

if low > high {

target not in array

search narrows until low > high, then returns -1

DSA Go

if low > high {

single element array with target present

mid equals low equals high, target found or not found accordingly

DSA Go

if arr[mid] == target {

When to Use This Pattern

When you need to find an item quickly in a sorted list, use recursive binary search because it efficiently halves the search space each step.

Common Mistakes

Mistake: Calculating mid as (low + high) can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly in recursive calls
Fix: Ensure recursive calls use mid-1 or mid+1 to shrink search range properly

Summary

It finds a target value in a sorted array by recursively checking the middle element and searching the half that may contain the target.

Use it when you have a sorted list and want to find an element quickly.

The key insight is that each step cuts the search space in half, making the search very fast.