package search

// BinarySearch takes sorted values, a desired value, and the index.
func BinarySearch(values []int, targetValue int) int {
    // already sorted
    // in middle, if you get to match, or go left, right,
    lower := 0
    upper := len(values)
    for upper > lower {
        index := lower + ((upper - lower) / 2)
        actualValue := values[index]
        if actualValue == targetValue {
            return index
        }
        if actualValue > targetValue {
            upper = index
        } else if lower == index {
            lower += 1
        } else {
            lower = index
        }
    }
    return -1
}

package srt

func BinarySearch[T comparable](x []T, y T, c Comparer[T]) int {
    max := len(x) - 1
    min := 0
    index := max / 2
    for {
        if c.Equals(x[min], y) {
            return min
        }
        if c.Equals(x[max], y) {
            return max
        }
        if c.Greater(x[min], y) || c.Less(x[max], y) {
            return -1
        }
        if c.Equals(x[index], y) {
            return index
        }
        if max-min <= 1 {
            return -1
        }
        if c.Less(x[index], y) {
            min = index
        } else {
            max = index
        }
        if max == min {
            return -1
        }
        index = min + (max-min)/2
    }
}

type Comparer[T any] interface {
    Equals(x T, y T) bool
    Less(x T, y T) bool
    Greater(x T, y T) bool
}

package bisect

type MODE int

const (
    EQUAL MODE = iota
    BEFORE
    AFTER
)

func IndexOf(x []int, v int) int {
    i, ok := closestIndex(x, v)
    if ok {
        return i
    }
    return -1
}

func Contains(x []int, v int) bool {
    _, ok := closestIndex(x, v)
    return ok
}

func IndexOfOrBefore(x []int, v int) int {
    i, _ := closestIndex(x, v)
    if i == -2 {
        return len(x)
    }
    if i == -1 {
        return 0
    }
    return i
}

func closestIndex(x []int, v int) (int, bool) {
    if x == nil || len(x) < 1 {
        return -1, false
    }
    if x[0] == v {
        return 0, true
    } else if x[0] > v {
        return -1, false
    }
    if x[len(x)-1] == v {
        return len(x) - 1, true
    } else if x[len(x)-1] < v {
        return -2, false
    }
    lo := 0
    hi := len(x)
    var mid int
    for hi-lo > 1 {
        mid = (lo + hi) / 2
        mv := x[mid]
        if v == mv {
            return mid, true
        }
        if v > mv {
            lo = mid
        }
        if v < mv {
            hi = mid
        }
    }
    return hi, false
}

package search;

public class Binary {
    public static int Search(int[] nums, int value, int start, int stop) {
        int lo = start;
        int hi = stop - 1;
        if (nums[lo] == value) {
            return lo;
        }
        if (nums[hi] == value) {
            return hi;
        }
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            int v = nums[mid];
            if (v == value) {
                return v;
            }
            if (v < value) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return -1;
    }
}