Searching

Binary Search First Occurrence

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

Algorithm

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.

Basic Implementation

basic.sh
Replay: real traced execution (multi-file project)
#!/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"

  1. arr ← [1, 2, 4, 4, 4, 7, 9], target ← 4, result ← -1

    1#!/usr/bin/env bash2set -euo pipefail
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

  2. hi ← 2, mid ← 3, result ← 3

    8while [ "$lo" -le "$hi" ]; do9	mid=$((lo + (hi - lo) / 2))10	if [ "${arr[mid]}" -eq "$target" ]; then
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    8while [ "$lo" -le "$hi" ]; do9	mid=$((lo + (hi - lo) / 2))10	if [ "${arr[mid]}" -eq "$target" ]; then
    values this step0 → 2lo1mid2hi3result

  4. hi ← 1, result ← 2, mid ← 2

    8while [ "$lo" -le "$hi" ]; do9	mid=$((lo + (hi - lo) / 2))10	if [ "${arr[mid]}" -eq "$target" ]; then
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    18done19echo "$result"
    values this step2stdout2result

Complexity

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

Implementation notes

  • arr=(1 2 4 4 4 7 9) is a Bash indexed array, and this lesson uses zero-based positions.
  • hi=$((${#arr[@]} - 1)) reads the array length with ${#arr[@]} and sets the initial upper bound to index 6.
  • lo=0, hi=6, and result=-1 seed the search window and the not-found sentinel.
  • mid=$((lo + (hi - lo) / 2)) computes the midpoint with Bash arithmetic expansion.
  • [ "${arr[mid]}" -eq "$target" ] tests for a numeric match, and [ "${arr[mid]}" -lt "$target" ] tests whether the current value is too small.
  • On a match, result=$mid records the current index, then hi=$((mid - 1)) keeps searching left for the first duplicate.
  • When the value is too small, lo=$((mid + 1)) moves the lower bound right.

Replay steps

start: lo=0, hi=6, result=-1
mid=3: arr[3]=4 matches -> result=3, hi=2
mid=1: arr[1]=2 is too small -> lo=2
mid=2: arr[2]=4 matches -> result=2, hi=1
stop:  lo=2, hi=1 -> print 2
  • echo "$result" prints exactly 2.