Searching

Binary Search (Recursive)

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

Algorithm

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.

Basic Implementation

basic.go
Replay: real traced execution (multi-file project)
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))
}

  1. lo ← 0, hi ← 6, target ← 11

    1package main
    values this step0lo6hi11target

  2. mid ← 3, arr[mid] ← 7, next call ← (4, 6)

    8}9mid := lo + (hi-lo)/210if arr[mid] == target {
    values this step3mid7arr[mid](4, 6)next call0lo6hi

  3. mid ← 5, arr[mid] ← 11, result ← 5

    8}9mid := lo + (hi-lo)/210if arr[mid] == target {
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    1package main
    values this step5stdout5result

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.