Binary Search (Iterative)

Halve a sorted array each step by comparing the middle element to the target. Tracks lo, hi, and mid indices iteratively and exits the moment a match lands.

Algorithm

Canonical input arr=(1 3 5 7 9 11 13) with target=11 matches at 0-indexed position 5 after two iterations.

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
arr=(1 3 5 7 9 11 13)
target=11
lo=0
hi=$(( ${#arr[@]} - 1 ))
result=-1
while [ "$lo" -le "$hi" ]; do
	mid=$(( lo + (hi - lo) / 2 ))
	if [ "${arr[mid]}" -eq "$target" ]; then
		result=$mid
		break
	fi
	if [ "${arr[mid]}" -lt "$target" ]; then
		lo=$((mid + 1))
	else
		hi=$((mid - 1))
	fi
done
echo "$result"

Complexity

Time: O(log n)
Space: O(1)

Implementation notes

Bash: explicit while [ "$lo" -le "$hi" ] with arithmetic mid=$(( lo + (hi - lo) / 2 )) keeps the halving step visible. The shell has no built-in sorted-array search; piping to grep -n or awk would skip the educational halving loop.
The branchy if [ ... ] -eq / -lt / else cascade mirrors the three-way decision in the lesson spec.
The replay shows lo, hi, mid, and arr[mid] on each frame plus the branch label (lo = mid + 1, hi = mid - 1, or match).

halving window `mid = lo + (hi - lo) / 2` keeps the index in bounds. Each branch either accepts `mid` as the answer or shrinks the window to one half.

iterative exit A `result=-1` sentinel and an explicit `break` after the match keep the loop iterative without recursion or exceptions.