Function lowerBound

dynamic/longestincreasingsubsequencegreedy.go:29–43

Function to find the leftmost index in arr with value >= val, mimicking the inbuild lower_bound function in C++ Time Complexity: O(logn) Auxiliary Space: O(1)

(arr []int, val int)

// Time Complexity: O(logn)
// Auxiliary Space: O(1)
func lowerBound(arr []int, val int) int {
	searchWindowLeft, searchWindowRight := 0, len(arr)-1

	for searchWindowLeft <= searchWindowRight {
		middle := (searchWindowLeft + searchWindowRight) / 2

		if arr[middle] < val {
			searchWindowLeft = middle + 1
		} else {
			searchWindowRight = middle - 1
		}
	}

	return searchWindowRight + 1
}