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.R

arr <- c(1, 2, 4, 4, 4, 7, 9)
target <- 4
lo <- 0
hi <- length(arr) - 1
result <- -1
while (lo <= hi) {
  mid <- lo + (hi - lo) %/% 2
  value <- arr[mid + 1]
  if (value == target) {
    result <- mid
    hi <- mid - 1
  } else if (value < target) {
    lo <- mid + 1
  } else {
    hi <- mid - 1
  }
}
cat(result, "\n", sep = "")

Complexity

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

Implementation notes

arr <- c(1, 2, 4, 4, 4, 7, 9) creates the sorted numeric R vector.
target <- 4 is the searched value.
Even though R vectors are 1-based, this lesson keeps the search bounds and result in zero-based positions: lo <- 0, hi <- length(arr) - 1, and result <- -1.
The actual R vector read compensates for that convention with value <- arr[mid + 1].
The loop runs while lo <= hi.
Midpoint calculation uses integer division: mid <- lo + (hi - lo) %/% 2.
Comparisons are scalar numeric checks: value == target and value < target.
On a match, result <- mid records the current zero-based index, then hi <- mid - 1 keeps searching the left side for the first copy.

Replay steps

start: lo=0, hi=6, result=-1
mid=3, arr[4]=4: match, result=3, hi=2
mid=1, arr[2]=2: too small, lo=2, result=3
mid=2, arr[3]=4: match, result=2, hi=1
stop: lo > hi, print 2

cat(result, "\n", sep = "") prints the final zero-based first occurrence, 2.

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

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