func binary_search(l, r int) int{
    for l < r:
        m := l + (r - l) // 2
        if f(m): return m  // optional
        if g(m):
            r = m // new range [l, m)
        else:
            l = m + 1 // new range [m+1, r)
    return l // or not found
}

// lowerBound first index of i, such that s[i] >= t
func lowerBound(s []int, t int) int {
	l := 0
	r := len(s)
	for l < r {
		m := l + (r-l)/2
		if s[m] >= t {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

// upperBound first index of i, such that s[i] > t
func upperBound(s []int, t int) int {
	l := 0
	r := len(s)
	for l < r {
		m := l + (r-l)/2
		if s[m] > t {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

func mySqrt(x int) int {
	l := 1
	r := x + 1
	for l < r {
		m := l + (r-l)/2
		if m*m > x {
			r = m
		} else {
			l = m + 1
		}
	}
	return l - 1
}

func firstBadVersion(n int) int {
	l := 0
	r := n
	for l < r {
		m := l + (r-l)/2
		if isBadVersion(m) {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

func maxInArr(nums []int) int {
	max := nums[0]
	for i := 1; i < len(nums); i++ {
		if max < nums[i] {
			max = nums[i]
		}
	}
	return max
}

func minEatingSpeed(piles []int, h int) int {
	l := 1
	r := maxInArr(piles) + 1

	for l < r {
		m := l + (r-l)/2
		_h := 0
		for _, p := range piles {
			_h += (p + m - 1) / m
		}
		if _h <= h {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

func kthSmallest(matrix [][]int, k int) int {
	l := matrix[0][0]
	x, y := len(matrix), len(matrix[0])
	r := matrix[x][y]
	for l < r {
		m := l + (r-l)/2
		total := 0
		for _, row := range matrix {
			total += upperBound(row, m)
		}
		if total >= k {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

func upperBound(s []int, t int) int {
	l := 0
	r := len(s)
	for l < r {
		m := l + (r-l)/2
		if s[m] > t {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}