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 Bash DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.sh
Replay: real traced execution (multi-file project)
#!/usr/bin/env bash
set -euo pipefail
arr=(1 3 5 7 9 11 13)
target=11
search() {
	local lo=$1
	local hi=$2
	if [ "$lo" -gt "$hi" ]; then
		echo -1
		return
	fi
	local mid=$((lo + (hi - lo) / 2))
	if [ "${arr[mid]}" -eq "$target" ]; then
		echo "$mid"
	elif [ "${arr[mid]}" -lt "$target" ]; then
		search $((mid + 1)) "$hi"
	else
		search "$lo" $((mid - 1))
	fi
}
search 0 $((${#arr[@]} - 1))

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

    1#!/usr/bin/env bash2set -euo pipefail
    values this step0lo6hi11target

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

    11fi12local mid=$((lo + (hi - lo) / 2))13if [ "${arr[mid]}" -eq "$target" ]; then
    values this step3mid7arr[mid](4, 6)next call0lo6hi

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

    11fi12local mid=$((lo + (hi - lo) / 2))13if [ "${arr[mid]}" -eq "$target" ]; then
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    13if [ "${arr[mid]}" -eq "$target" ]; then14	echo "$mid"15elif [ "${arr[mid]}" -lt "$target" ]; then
    values this step5stdout5result

Complexity

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

Implementation notes

  • arr=(1 3 5 7 9 11 13) is a Bash indexed array, and target=11 is a scalar shell variable.
  • search() receives the current bounds as arguments. Inside the function, local lo=$1 and local hi=$2 keep each recursive call's window separate.
  • The base case is [ "$lo" -gt "$hi" ]; if the window is empty, the function prints -1 and returns.
  • mid=$((lo + (hi - lo) / 2)) computes the midpoint with Bash arithmetic expansion.
  • [ "${arr[mid]}" -eq "$target" ] is the numeric match test.
  • [ "${arr[mid]}" -lt "$target" ] is the numeric "go right" test.
  • If the value is too small, search $((mid + 1)) "$hi" recurses on the right half.
  • Otherwise, search "$lo" $((mid - 1)) recurses on the left half.
  • Results are returned through echo, so the matching branch prints echo "$mid".

Replay steps

search(0, 6): mid=3, arr[3]=7 -> recurse right to search(4, 6)
search(4, 6): mid=5, arr[5]=11 -> echo 5
  • The top-level call is search 0 $((${#arr[@]} - 1)), and the checked output is 5.