binsearch.go2

package main

// vim:set ft=go:

// snip ------------------------------------------------------------------------

// BinSearch returns the i that pred(i) == 0.
// When not found, it returns the r.
//
// Note:
//   If pred(i) < 0, BinSearch will search integers less than i.
//   If pred(i) > 0, BinSearch will search integers greater than i.
func BinSearch(l, r int, pred func(int) int) int {
	ll := l - 1
	rr := r
	for 1 < abs(ll-rr) {
		m := binsearch_median(ll, rr)
		p := pred(m)
		if p == 0 {
			return m
		} else if p < 0 {
			rr = m
		} else {
			ll = m
		}
	}
	return r
}

// LowerBound searches lowest number i that pred(i) => true in range [l, r)
func LowerBound(l, r int, pred func(i int) bool) int {
	ng := l - 1
	ok := r
	for 1 < abs(ng-ok) {
		m := binsearch_median(ng, ok)
		if pred(m) {
			ok = m
		} else {
			ng = m
		}
	}
	return ok
}

// UpperBound searches highest number i+1 that pred(i) => true in range [l, r)
func UpperBound(l, r int, pred func(i int) bool) int {
	ok := l - 1
	ng := r
	for 1 < abs(ok-ng) {
		m := binsearch_median(ng, ok)
		if pred(m) {
			ok = m
		} else {
			ng = m
		}
	}
	return ng
}

// EqualRange returns the lowest number and i that pred(i) == 0 and the highest
// number j+1 that pred(j) == 0
func EqualRange(l, r int, pred func(i int) int) (int, int) {
	low := LowerBound(l, r, func(i int) bool {
		return pred(i) <= 0
	})
	high := UpperBound(l, r, func(i int) bool {
		return 0 <= pred(i)
	})
	return low, high
}

// Return the median of l and r
func binsearch_median(l, r int) int {
	if (l < 0 && r < 0) || (0 <= l && 0 <= r) {
		// Equivalent to (l+r)/2 but this avoids overflow with
		// large abs(l) and abs(r).
		return l + (r-l)/2
	}
	// for math.MinInt64 and math.MaxInt64
	return l/2 + r/2
}

func LinearSearch(l, r int, pred func(int) int) int {
	var i int
	for i = l; i < r; i++ {
		if pred(i) == 0 {
			return i
		}
	}
	return i
}

func LinearLowerBound(l, r int, pred func(int) bool) int {
	var i int
	for i = l; i < r; i++ {
		if pred(i) {
			return i
		}
	}
	return i
}

func LinearUpperBound(l, r int, pred func(int) bool) int {
	var i int
	for i = l; i < r; i++ {
		if !pred(i) {
			return i
		}
	}
	return i
}

func LinearEqualRange(l, r int, pred func(int) int) (int, int) {
	var i int
	for i = l; i < r && 0 < pred(i); i++ {
	}
	lb := i
	for i < r && pred(i) == 0 {
		i++
	}
	return lb, i
}