给一个升序数组，找到 target 最后一次出现的位置，如果没出现过返回 -1

点此做题

样例 1：

输入：nums = [1,2,2,4,5,5], target = 2 输出：2 

样例 2：

输入：nums = [1,2,2,4,5,5], target = 6 输出：-1 

算法：二分

算法思路

• 题目要求我们找到 target 最后一次出现的位置，由于数组是有序数组，我们可以考虑使用二分法来查找

代码思路

1. 设置左边界等于 0，右边界等于 numsLen – 1
2. 对于 mid 所指向的数，当 target < nums[mid]时，说明 target 在 mid 左侧，那么 right = mid ；否则说明 target 在 mid 右侧，或者如果 target == nums[mid]的话说明 mid 还有可能存在 target 那么 left = mid
3. 不断重复 2 直到 left + 1 == right 退出
4. 判断 nums[right]是否等于 target，若等于返回 right，否则返回 left，注意一定要先判 nums[right]，因为 nums[left]可能也等于 target，但不是最后的位置

复杂度分析

NN 表示 nums 数组长度

• 空间复杂度：O(1)
• 时间复杂度：O(logN)

public class Solution {      /**      * @param nums: An integer array sorted in ascending order      * @param target: An integer      * @return: An integer      */      public int lastPosition(int[] nums, int target) {         if(nums == null || nums.length == 0)             return -1;         if(target < nums[0] || target > nums[nums.length-1])             return -1;          int left = 0, right = nums.length-1;          while(left+1 < right){             int mid = left + (right - left) / 2;             if(nums[mid] > target)                 right = mid;             else                  left = mid;         }          if(nums[right] == target)             return right;         if(nums[left] == target)             return left;         return -1;     } }