// Week 2 – Linear search in three variants, counting comparisons
// Run: go run ./w02/linearsearch
package main

import "fmt"

var comparisons int // number of conditions (comparisons) evaluated

// count counts the evaluated conditions.
func count(b bool) bool {
	comparisons++
	return b
}

// linearSearch returns the index of x, or -1.
//
//	Pseudocode (indexing from 1):
//	  i ← 1
//	  While i ≤ n and A[i] ≠ x : i ← i + 1
//	  If i ≤ n then Return i else Return 0
func linearSearch(a []int, x int) int {
	i := 0
	for count(i < len(a)) && count(a[i] != x) {
		i++
	}
	if i < len(a) {
		return i
	}
	return -1
}

// sentinelSearch: the value we look for is placed at the end of the slice (a[n]) as a sentinel,
// so the loop does not check the index bound (about n comparisons instead of 2n).
func sentinelSearch(a []int, n, x int) int {
	a[n] = x
	i := 0
	for count(a[i] != x) {
		i++
	}
	if i < n {
		return i
	}
	return -1
}

// sortedLinearSearch: in a sorted slice we stop at the first element greater than x.
func sortedLinearSearch(a []int, x int) int {
	i := 0
	for count(i < len(a)) && count(a[i] < x) {
		i++
	}
	if count(i < len(a)) && count(a[i] == x) {
		return i
	}
	return -1
}

func main() {
	a := []int{8, 3, 12, 5, 9, 1, 7}

	comparisons = 0
	fmt.Printf("linearSearch(9)  = %d  (%d comparisons)\n", linearSearch(a, 9), comparisons)
	comparisons = 0
	fmt.Printf("linearSearch(4)  = %d (%d comparisons)\n", linearSearch(a, 4), comparisons)

	b := []int{8, 3, 12, 5, 9, 1, 7, 0} // the last slot is for the sentinel
	comparisons = 0
	fmt.Printf("sentinelSearch(4) = %d (%d comparisons)\n", sentinelSearch(b, 7, 4), comparisons)

	sorted := []int{1, 3, 5, 7, 8, 9, 12}
	comparisons = 0
	fmt.Printf("sortedLinearSearch(4) = %d (%d comparisons)\n", sortedLinearSearch(sorted, 4), comparisons)

	n := 1000
	big := make([]int, n)
	for i := range big {
		big[i] = i
	}
	comparisons = 0
	for i := 0; i < n; i++ {
		linearSearch(big, i)
	}
	fmt.Printf("n = %d, successful search: on average %.1f comparisons (≈ n/2 steps, 2 per step)\n",
		n, float64(comparisons)/float64(n))
}