Array Upper Bound — LeetCode 2774 Python Solution

The problem

Write code that enhances all arrays such that you can call the upperBound() method on any array and it will return the last index of a given target number. nums is a sorted ascending array of numbers that may contain duplicates.

Example

Input

nums = [3,4,5], target = 5

Output

2

Explanation

Last index of target value is 2

Python solution

class Solution:
    def upperBound(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= target:
                lo = mid + 1
            else:
                hi = mid
        idx = lo - 1
        return idx if idx >= 0 and nums[idx] == target else -1

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 2774. Array Upper Bound is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems