// Week 2 – Solutions of the practice exercises
// Run: go run ./w02/exercises
package main

import "fmt"

// E1. Maximum selection – O(n).
func maxIndex(a []int) int {
	max := 0
	for i := 1; i < len(a); i++ {
		if a[i] > a[max] {
			max = i
		}
	}
	return max
}

// E2. Counting – O(n).
func countOf(a []int, x int) int {
	c := 0
	for _, v := range a {
		if v == x {
			c++
		}
	}
	return c
}

// E3. First occurrence in a sorted slice – O(log n).
func firstOccurrence(a []int, x int) int {
	lo, hi, result := 0, len(a)-1, -1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if a[mid] == x {
			result = mid
			hi = mid - 1 // continue searching to the left
		} else if a[mid] < x {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	return result
}

// E4. Insertion position: the first index where a[i] >= x – O(log n).
func lowerBound(a []int, x int) int {
	lo, hi := 0, len(a) // [lo, hi)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if a[mid] < x {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

// E5. Integer square root by binary search.
func isqrt(n int64) int64 {
	var lo, hi, r int64 = 0, n, 0
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if mid == 0 || mid <= n/mid {
			r = mid
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	return r
}

// E6. Guess the number: how many questions are needed?
func guessSteps(secret, max int) int {
	lo, hi, steps := 1, max, 0
	for {
		mid := lo + (hi-lo)/2
		steps++
		if mid == secret {
			return steps
		}
		if mid < secret {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
}

func main() {
	a := []int{4, 9, 2, 9, 7, 1, 9}
	fmt.Println("E1. maxIndex =", maxIndex(a))
	fmt.Println("E2. countOf(9) =", countOf(a, 9))
	s := []int{1, 2, 2, 2, 5, 7, 7, 9}
	fmt.Println("E3. firstOccurrence(2) =", firstOccurrence(s, 2), ", firstOccurrence(7) =", firstOccurrence(s, 7))
	fmt.Println("E4. lowerBound(6) =", lowerBound(s, 6), ", lowerBound(0) =", lowerBound(s, 0), ", lowerBound(10) =", lowerBound(s, 10))
	fmt.Println("E5. isqrt(99) =", isqrt(99), ", isqrt(1e12) =", isqrt(1_000_000_000_000))
	worst := 0
	for sec := 1; sec <= 1000; sec++ {
		worst = max(worst, guessSteps(sec, 1000))
	}
	fmt.Println("E6. between 1 and 1000 at most", worst, "questions are needed")
}