Find the last position of a target number in a sorted array. Return -1 if target does not exist.

Have you met this question in a real interview?

Yes

Example

Given[1, 2, 2, 4, 5, 5].

For target =2, return 2.

For target =5, return 5.

For target =6, return -1.

分析： 本题关键是如果找到mid = target， 循环不能停，要把begin + mid继续下去，因为题目要找的是最后一个，不是随意一个

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) {
        // Write your code here

        if(nums == null || nums.length == 0){
            return -1;
        }

        int begin = 0;
        int end = nums.length-1;
        while(begin + 1 < end){
            int mid = begin + (end - begin)/2;
            if(nums[mid] > target){
                end = mid;
            }else{
                begin = mid; 
            }
        }

        if(nums[end] == target){
            return end;
        }else if(nums[begin] == target){
            return begin;
        }

        return -1;
    }
}