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

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)
}

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