Go Program for Binary Search Using Recursion

A Go program for binary search using recursion defines a function like func binarySearch(arr []int, low, high, target int) int that calls itself to search halves of the sorted array until it finds the target or returns -1.

Examples

Inputarr = [1, 3, 5, 7, 9], target = 7

Output3

Inputarr = [2, 4, 6, 8, 10], target = 5

Output-1

Inputarr = [10], target = 10

Output0

How to Think About It

To do a binary search with recursion, start by checking the middle element of the sorted list. If it matches the target, return its position. If the target is smaller, search the left half by calling the function again with updated boundaries. If larger, search the right half similarly. Repeat until the target is found or the search space is empty.

Algorithm

1

Check if low index is greater than high index; if yes, return -1 (target not found).

2

Calculate middle index as (low + high) / 2.

3

If element at middle equals target, return middle index.

4

If target is less than middle element, recursively search left half (low to middle-1).

5

If target is greater than middle element, recursively search right half (middle+1 to high).

Code

go

package main

import "fmt"

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

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

Output

3

Dry Run

Let's trace searching for 7 in [1, 3, 5, 7, 9] through the code

1

Initial call

low=0, high=4, mid=2, arr[mid]=5, target=7

2

Target greater than mid element

Call binarySearch(arr, 3, 4, 7)

3

Second call

low=3, high=4, mid=3, arr[mid]=7, target=7

4

Target found

Return index 3

Call	low	high	mid	arr[mid]	target	Action
1	0	4	2	5	7	Search right half
2	3	4	3	7	7	Found target

Why This Works

Step 1: Divide the array

The code finds the middle index by (low + high) / 2 to split the array into halves.

Step 2: Compare middle element

It compares the middle element with the target using ==, <, or > to decide which half to search next.

Step 3: Recursive calls

The function calls itself with updated low and high indexes to search the correct half until the target is found or the search space is empty.

Alternative Approaches

Iterative binary search

go

package main

import "fmt"

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

func main() {
    arr := []int{1, 3, 5, 7, 9}
    target := 7
    fmt.Println(binarySearchIter(arr, target))
}

Uses a loop instead of recursion, which can be more memory efficient by avoiding call stack overhead.

Binary search using slices

go

package main

import "fmt"

func binarySearchSlice(arr []int, target int) int {
    if len(arr) == 0 {
        return -1
    }
    mid := len(arr) / 2
    if arr[mid] == target {
        return mid
    } else if target < arr[mid] {
        return binarySearchSlice(arr[:mid], target)
    } else {
        res := binarySearchSlice(arr[mid+1:], target)
        if res == -1 {
            return -1
        }
        return mid + 1 + res
    }
}

func main() {
    arr := []int{1, 3, 5, 7, 9}
    target := 7
    fmt.Println(binarySearchSlice(arr, target))
}

Uses array slicing to reduce the search space but can be less efficient due to creating new slices.

Complexity: O(log n) time, O(log n) space

Time Complexity

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

Space Complexity

Recursive calls add to the call stack, so space complexity is O(log n) due to recursion depth.

Which Approach is Fastest?

Iterative binary search uses O(1) space and is generally faster in practice due to no recursion overhead.

Approach	Time	Space	Best For
Recursive binary search	O(log n)	O(log n)	Clear recursive logic, teaching
Iterative binary search	O(log n)	O(1)	Performance and memory efficiency
Binary search with slices	O(log n)	O(log n)	Simpler code but less memory efficient