Searching

Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

Basic Implementation

basic.go 
package main

import "fmt"

func search(arr []int, target int, lo int, hi int) int {
	if lo > hi {
		return -1
	}
	mid := lo + (hi-lo)/2
	if arr[mid] == target {
		return mid
	}
	if arr[mid] < target {
		return search(arr, target, mid+1, hi)
	}
	return search(arr, target, lo, mid-1)
}

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

Complexity

  • Time: O(log n)
  • Space: O(log n) call stack

Implementation notes

  • Go builds the sorted input with arr := []int{1, 3, 5, 7, 9, 11, 13}; the recursive search reads through the slice header and does not mutate the backing array.
  • search(arr []int, target int, lo int, hi int) int carries the window as int bounds. main starts the call with 0 and len(arr)-1.
  • The base case returns -1 when lo > hi. Otherwise mid := lo + (hi-lo)/2 selects the checked index for the current frame.
  • The branch order returns immediately on equality, recurses right when arr[mid] < target, and otherwise recurses left. Each recursive call returns its integer result directly to the caller.
  • The trace records lo=0, hi=6, then mid=3 with arr[mid]=7 and the next call (4, 6). In that frame mid=5 matches 11, returns 5, and fmt.Println(search(...)) prints 5.
  • The shrinking bounds keep mid within the slice for this input; Go still performs normal bounds checks. The visible extra runtime state is the small chain of recursive stack frames carrying arr, target, lo, and hi.
execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.
cross-language comparison This Go DSA version keeps the same data and final output as every other DSA book in this wave.