// 2. hét – Bináris keresés rendezett szeletben
// Futtatás: go run ./h02/binarysearch
package main

import (
	"fmt"
	"sort"
)

// binarySearch visszaadja x indexét, vagy -1-et.
//
//	Pszeudokód (1-től indexelve):
//	  bal ← 1 ; jobb ← n
//	  Ciklus amíg bal ≤ jobb
//	    k ← (bal + jobb) div 2
//	    Ha A[k] = x akkor Vissza: k
//	    különben ha A[k] < x akkor bal ← k + 1
//	    különben jobb ← k − 1
//	  Ciklus vége
//	  Vissza: 0
func binarySearch(a []int, x int) int {
	lo, hi := 0, len(a)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2 // (lo+hi)/2 nagy indexeknél túlcsordulhat
		switch {
		case a[mid] == x:
			return mid
		case a[mid] < x:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return -1
}

func binarySearchTrace(a []int, x int) int {
	lo, hi, step := 0, len(a)-1, 1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		fmt.Printf("  %d. lépés: lo=%d hi=%d mid=%d a[mid]=%d\n", step, lo, hi, mid, a[mid])
		step++
		if a[mid] == x {
			return mid
		}
		if a[mid] < x {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	return -1
}

// worstCaseSteps: legrosszabb esetben hány lépés kell n elemnél (≈ log2 n + 1).
func worstCaseSteps(n int) int {
	steps := 0
	for n > 0 {
		n /= 2
		steps++
	}
	return steps
}

func main() {
	a := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	fmt.Println("Keresés: 23")
	fmt.Println("  eredmény: index", binarySearchTrace(a, 23))
	fmt.Println("Keresés: 40")
	fmt.Println("  eredmény: index", binarySearchTrace(a, 40))

	fmt.Println()
	fmt.Println("Legrosszabb eset lépésszáma:")
	fmt.Println("             n       lineáris   bináris")
	for _, n := range []int{10, 100, 1_000, 1_000_000, 1_000_000_000} {
		fmt.Printf("%14d %14d %9d\n", n, n, worstCaseSteps(n))
	}

	// A Go beépített változata (sort csomag)
	i := sort.SearchInts(a, 56)
	fmt.Println()
	fmt.Println("sort.SearchInts(a, 56) =", i)
}