package main

import "fmt"

func linearSearch(values []int, target int) (index, comparisons int) {
	for index, value := range values {
		comparisons++
		if value == target {
			return index, comparisons
		}
	}
	return -1, comparisons
}

func countEqualPairs(values []int) (pairs, comparisons int) {
	for i := 0; i < len(values); i++ {
		for j := i + 1; j < len(values); j++ {
			comparisons++
			if values[i] == values[j] {
				pairs++
			}
		}
	}
	return pairs, comparisons
}

func main() {
	values := []int{0, 1, 2, 3, 4, 5, 6, 7}
	index, comparisons := linearSearch(values, 0)
	fmt.Printf("first: index=%d comparisons=%d\n", index, comparisons)
	index, comparisons = linearSearch(values, -1)
	fmt.Printf("missing: index=%d comparisons=%d\n", index, comparisons)

	// These small inputs keep all counters within the range of int.
	for _, size := range []int{8, 64, 1024} {
		input := make([]int, size)
		for i := range input {
			input[i] = i
		}
		_, linearComparisons := linearSearch(input, -1)
		pairs, pairComparisons := countEqualPairs(input)
		fmt.Printf("n=%d linear=%d pair-checks=%d matches=%d\n",
			size, linearComparisons, pairComparisons, pairs)
	}
}
