Array Upper Bound

Problem Statement

The task is to implement a method named upperBound() for arrays which efficiently finds the last index of a specified target number within an array. The arrays in question, nums, are sorted in ascending order and may contain repeated elements. The upperBound() method should return the last position of the target number if it is present in the array. However, if the target number does not exist in the array, the function should return -1. The primary challenge here is implementing this search functionality in an optimized way, considering the possible large size of the input arrays and leveraging the sorted property of the arrays.

Examples

Example 1

Input:

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

Output:

2

Explanation:

Last index of target value is 2

Example 2

Input:

nums = [1,4,5], target = 2

Output:

-1

Explanation:

Because there is no digit 2 in the array, return -1.

Example 3

Input:

nums = [3,4,6,6,6,6,7], target = 6

Output:

5

Explanation:

Last index of target value is 5

Constraints

• 1 <= nums.length <= 104
• -104 <= nums[i], target <= 104
• nums is sorted in ascending order.

Approach and Intuition

The functionality of upperBound() is to locate the last occurrence of the target value in a sorted array. Understanding and using the properties of the sorted array can make this search efficient:

1. Binary Search Approach:

   • Using a modified binary search algorithm provides a logarithmic time complexity, which is suitable for constraints where the array length can go up to 10,000 elements. Instead of searching for the first occurrence of the target, we adapt the binary search to continue searching to the right, even after finding the target, to ensure we get the last occurrence.
   • Initialize low to 0 and high to nums.length - 1. While low is less than or equal to high, calculate the mid index.
   • If nums[mid] is less than the target, move the low pointer to mid + 1. If nums[mid] equals the target, set an answer variable to mid and move the low pointer to mid + 1 to continue searching on the right side.
   • If nums[mid] is greater than the target, move the high pointer to mid - 1.
   • If the search completes and the target was found, return the position stored in the answer variable. If the target was not found at all, return -1.

2. Edge Cases Handling:

   • When the array has only one element, directly check if it is equal to the target.
   • If the target is outside the minimum and maximum bounds of the array, immediately return -1, thereby improving the efficiency by avoiding unnecessary search.
   • Ensure that the method efficiently handles arrays where all elements are the same as the target or none of the elements is the target.

This upperBound() method leveraging a modified binary search exploits the fact that the input array is sorted, providing both efficient and clear handling of various scenarios detailed by the constraints.

Solutions

Array.prototype.findUpperBound = function(value) {
    return this.lastIndexOf(value);
};

let numbers = [1, 2, 4, 4, 4, 5, 6];
console.log(numbers.findUpperBound(4));  // Output: 4