// Week 2 – Measuring running time: O(n), O(log n) and O(n²)
// Run: go run ./w02/timing
package main

import (
	"fmt"
	"time"
)

func linearSearch(a []int, x int) int {
	for i, v := range a {
		if v == x {
			return i
		}
	}
	return -1
}

func binarySearch(a []int, x int) int {
	lo, hi := 0, len(a)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if a[mid] == x {
			return mid
		}
		if a[mid] < x {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	return -1
}

// hasDuplicate – O(n²): examines every pair.
func hasDuplicate(a []int) bool {
	for i := 0; i < len(a); i++ {
		for j := i + 1; j < len(a); j++ {
			if a[i] == a[j] {
				return true
			}
		}
	}
	return false
}

func main() {
	fmt.Println("1000 searches (worst case: the value is not in the slice)")
	fmt.Println("         n     linear (ms)    binary (ms)")
	for n := 1_000; n <= 10_000_000; n *= 10 {
		a := make([]int, n)
		for i := range a {
			a[i] = 2 * i
		}
		t0 := time.Now()
		for r := 0; r < 1000; r++ {
			linearSearch(a, -1)
		}
		t1 := time.Now()
		for r := 0; r < 1000; r++ {
			binarySearch(a, -1)
		}
		t2 := time.Now()
		fmt.Printf("%10d %15.2f %14.4f\n", n,
			float64(t1.Sub(t0).Microseconds())/1000, float64(t2.Sub(t1).Nanoseconds())/1e6)
	}

	fmt.Println()
	fmt.Println("hasDuplicate – O(n²): when n doubles, the time roughly quadruples")
	for n := 5_000; n <= 40_000; n *= 2 {
		a := make([]int, n)
		for i := range a {
			a[i] = i
		}
		t0 := time.Now()
		hasDuplicate(a)
		fmt.Printf("  n = %6d: %8.1f ms\n", n, float64(time.Since(t0).Microseconds())/1000)
	}
}