Binary Search on the Boundary

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {

}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
    for lo < hi {
        mid := lo + (hi-lo)/2
    }
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
    for lo < hi {
        mid := lo + (hi-lo)/2

            // mid is too small, so the answer is strictly to its right.
            // mid might BE the boundary, so keep it in range (hi = mid, not mid-1).
    }
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
    for lo < hi {
        mid := lo + (hi-lo)/2

        if nums[mid] < target {
            // mid is too small, so the answer is strictly to its right.
            lo = mid + 1
        } else {
            // mid might BE the boundary, so keep it in range (hi = mid, not mid-1).
            hi = mid
        }
    }
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
    for lo < hi {
        mid := lo + (hi-lo)/2

        if nums[mid] < target {
            // mid is too small, so the answer is strictly to its right.
            lo = mid + 1
        } else {
            // mid might BE the boundary, so keep it in range (hi = mid, not mid-1).
            hi = mid
        }
    }

    // lo == hi: the first position where target could be inserted in order.
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
    for lo < hi {
        mid := lo + (hi-lo)/2

        if nums[mid] < target {
            // mid is too small, so the answer is strictly to its right.
            lo = mid + 1
        } else {
            // mid might BE the boundary, so keep it in range (hi = mid, not mid-1).
            hi = mid
        }
    }

    // lo == hi: the first position where target could be inserted in order.
    return lo
}

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
    for lo < hi {
        mid := lo + (hi-lo)/2

        if nums[mid] < target {
            // mid is too small, so the answer is strictly to its right.
            lo = mid + 1
        } else {
            // mid might BE the boundary, so keep it in range (hi = mid, not mid-1).
            hi = mid
        }
    }

    // lo == hi: the first position where target could be inserted in order.
    return lo
}

// upperBound returns the first index i with nums[i] > target. The ONLY change
// from lowerBound is <= instead of <, which steps past equal elements too.

// lowerBound returns the first index i with nums[i] >= target
// (or len(nums) if every element is smaller). This is Go's sort.SearchInts.
func lowerBound(nums []int, target int) int {
    // Half-open window [lo, hi). hi starts at len so "not found" can return it.
    lo, hi := 0, len(nums)

    // Note: lo < hi (not <=), because hi is exclusive.
    for lo < hi {
        mid := lo + (hi-lo)/2

        if nums[mid] < target {
            // mid is too small, so the answer is strictly to its right.
            lo = mid + 1
        } else {
            // mid might BE the boundary, so keep it in range (hi = mid, not mid-1).
            hi = mid
        }
    }

    // lo == hi: the first position where target could be inserted in order.
    return lo
}

// upperBound returns the first index i with nums[i] > target. The ONLY change
// from lowerBound is <= instead of <, which steps past equal elements too.
func upperBound(nums []int, target int) int {
    lo, hi := 0, len(nums)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if nums[mid] <= target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}