package binarysearch

import "strconv"

// SearchInts searches a slice of ints for the first position that 'n' should
// be inserted at and keep 'hay' sorted
func SearchInts(hay []int, n int) int {
	if len(hay) == 0 || n < hay[0] {
		return 0
	}
	if n > hay[len(hay)-1] {
		return len(hay)
	}

	mid := len(hay) / 2
	if hay[mid] < n {
		return mid + 1 + SearchInts(hay[mid+1:], n)
	}

	if n < hay[mid] {
		return SearchInts(hay[:mid], n)
	}

	for mid > 0 && hay[mid-1] == n {
		mid--
	}
	return mid
}

// Message does the binary search and returns an english string representation
// of the result
func Message(hay []int, n int) string {
	if len(hay) == 0 {
		return "slice has no values"
	}
	v := SearchInts(hay, n)
	if v < len(hay) && hay[v] == n {
		switch v {
		case 0:
			return itoa(n) + " found at beginning of slice"
		case len(hay) - 1:
			return itoa(n) + " found at end of slice"
		}
		return itoa(n) + " found at index " + itoa(v)
	}
	switch v {
	case 0:
		return itoa(n) + " < all values"
	case len(hay):
		return itoa(n) + " > all " + itoa(len(hay)) + " values"
	}
	return itoa(n) + " > " + itoa(hay[v-1]) + " at index " + itoa(v-1) + ", < " + itoa(hay[v]) + " at index " + itoa(v)
}

// itoa is because I'm tired of writing strconv.Itoa
func itoa(v int) string {
	return strconv.Itoa(v)
}