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

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"

The pinned run searches for 11 in [1, 3, 5, 7, 9, 11, 13]. The diagrams highlight the inclusive [lo, hi] window and each midpoint.

Step 1 - First midpoint is too small

lo = 0, hi = 6, mid = 3, and arr[3] = 7 is below target 11.

Step 2 - Window narrows to the right

Because 7 < 11, set lo = 4 and keep hi = 6.

Step 3 - Second midpoint matches

Now mid = 5 and arr[5] = 11, so the algorithm returns index 5.

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.