// 第 2 周 – 顺序查找的三种写法，统计比较次数
// 运行：go run ./w02/linearsearch
package main

import "fmt"

var comparisons int // 计算过的条件（比较）个数

// count 统计计算过的条件。
func count(b bool) bool {
	comparisons++
	return b
}

// linearSearch 返回 x 的下标，找不到时返回 -1。
//
//	伪代码（下标从 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：把要找的值作为哨兵放在切片末尾（a[n]），
// 这样循环就不必检查下标边界（大约 n 次比较，而不是 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：在有序切片中遇到第一个大于 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} // 最后一个位置留给哨兵
	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))
}