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 Go DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.go
Replay: real traced execution (multi-file project)
package main

import "fmt"

func main() {
	arr := []int{1, 2, 4, 4, 4, 7, 9}
	target := 4
	lo := 0
	hi := len(arr) - 1
	result := -1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if arr[mid] == target {
			result = mid
			hi = mid - 1
		} else if arr[mid] < target {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	fmt.Println(result)
}

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

    1package main
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

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

    11for lo <= hi {12	mid := lo + (hi-lo)/213	if arr[mid] == target {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    11for lo <= hi {12	mid := lo + (hi-lo)/213	if arr[mid] == target {
    values this step0 → 2lo1mid2hi3result

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

    11for lo <= hi {12	mid := lo + (hi-lo)/213	if arr[mid] == target {
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    1package main
    values this step2stdout2result

Complexity

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

Implementation notes

  • Go builds the sorted input with arr := []int{1, 2, 4, 4, 4, 7, 9}; the search reads from that slice's backing array and never mutates it.
  • lo, hi, mid, and result are int values. The midpoint uses lo + (hi-lo)/2, so the trace follows the changing window rather than relying on a library search helper.
  • result := -1 is the not-found sentinel. On equality the code records result = mid and then sets hi = mid - 1, which is why duplicates at indices 2, 3, and 4 still return the first index.
  • The branch order checks equality first, then arr[mid] < target, otherwise narrowing the high bound. The for lo <= hi guard keeps each indexed read in range for this input; Go still applies normal slice bounds checks.
  • The replay records mid=3 as a match (result=3, hi=2), then mid=1 with value 2 (lo=2), then mid=2 as the leftmost match (result=2, hi=1). fmt.Println(result) prints 2.