// Week 2 – Binary search in a sorted slice
// Run: go run ./w02/binarysearch
package main

import (
	"fmt"
	"sort"
)

// binarySearch returns the index of x, or -1.
//
//	Pseudocode (indexing from 1):
//	  lo ← 1 ; hi ← n
//	  While lo ≤ hi
//	    k ← (lo + hi) div 2
//	    If A[k] = x then Return k
//	    else if A[k] < x then lo ← k + 1
//	    else hi ← k − 1
//	  End while
//	  Return 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 may overflow for large indexes
		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("  step %d: 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: the number of steps needed in the worst case for n elements (≈ 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("Searching for 23")
	fmt.Println("  result: index", binarySearchTrace(a, 23))
	fmt.Println("Searching for 40")
	fmt.Println("  result: index", binarySearchTrace(a, 40))

	fmt.Println()
	fmt.Println("Number of steps in the worst case:")
	fmt.Println("             n         linear    binary")
	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))
	}

	// The built-in Go version (sort package)
	i := sort.SearchInts(a, 56)
	fmt.Println()
	fmt.Println("sort.SearchInts(a, 56) =", i)
}