Searching

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

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