We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Array Upper Bound

Number: 2768

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

Given a sorted (in ascending order) array of numbers that may contain duplicates, implement a method named upperBound() that returns the last index of a given target number. If the target number is not present, return -1.

Key Insights

  • The array is sorted, which allows us to use binary search to achieve O(log n) runtime.
  • The goal is to find the rightmost (last) occurrence of the target if it exists.
  • If the target does not exist in the array, the function should return -1.

Space and Time Complexity

Time Complexity: O(log n) Space Complexity: O(1)

Solution

We can solve this problem using a binary search variant designed to find the last occurrence of the target:

  1. Initialize two pointers, low and high, to the start and end of the array.
  2. Repeatedly compute the middle index.
  3. If the target is found, move the low pointer to search to the right to ensure it is the last occurrence.
  4. If the target is less than the middle element, adjust the high pointer.
  5. If the target is greater than the middle element, adjust the low pointer.
  6. After binary search terminates, verify whether the found index contains the target.
  7. Return the index if found; otherwise, return -1.

This approach uses no extra space (apart from a few variables) and performs in logarithmic time.

Code Solutions

# Function to find the last index of target in a sorted array
def upper_bound(nums, target):
    low = 0
    high = len(nums) - 1
    result = -1  # Default result if target not found
    
    # Binary search for the last occurrence of target
    while low <= high:
        mid = (low + high) // 2  # Compute mid index
        if nums[mid] == target:
            result = mid    # Record index of target found
            low = mid + 1   # Search right to find later occurrence
        elif nums[mid] < target:
            low = mid + 1   # Target is in the right half
        else:
            high = mid - 1  # Target is in the left half
    return result

# Example usage
print(upper_bound([3,4,5], 5))   # Output: 2
print(upper_bound([1,4,5], 2))   # Output: -1
print(upper_bound([3,4,6,6,6,6,7], 6)) # Output: 5
← Back to All Questions