Binary Search First Occurrence

Find the first copy of a duplicated target by recording matches and continuing to search the left half.

Algorithm

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
arr=(1 2 4 4 4 7 9)
target=4
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
		hi=$((mid - 1))
	elif [ "${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

Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
The final output is intentionally small and deterministic for cross-language comparison.

execution replay The checked-in replay follows the language-neutral state table for `search-binary-first`.

cross-language comparison This Bash DSA version keeps the same data and final output as every other DSA book in this wave.