Last Position of Target

题目位置
https://www.lintcode.com/problem/last-position-of-target/description

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

Example

• Example 1:
  Input: nums = [1,2,2,4,5,5], target = 2
  Output: 2
• Example 2:
  Input: nums = [1,2,2,4,5,5], target = 6
  Output: -1

题目分析
给定一个升序的排序数组（数组中可能存在重复元素）和一个target，找target在数组中出现的最后一个位置。

注意

• 当nums[mid] == target的时候，需要将start = mid，因为如果把end = mid的话，万一mid之后还有等于target的元素，就无法找到它们了。
• 对于找last position的情况，在跳出循环之后做判断的时候，先判断end，再判断start。

参考代码
java版本

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 start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = (start + end) / 2;
            if (nums[mid] == target) {
                start = mid;
            }
            else if (nums[mid] < target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        
        if (nums[end] == target) {
            return end;
        }
        if (nums[start] == target) {
            return start;
        }
        return -1;
    }
}

python版本

class Solution:
    """
    @param nums: An integer array sorted in ascending order
    @param target: An integer
    @return: An integer
    """
    def lastPosition(self, nums, target):
        # write your code here
        if nums is None or len(nums) == 0:
            return -1
        start = 0
        end = len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if nums[mid] <= target:
                start = mid
            else:
                end = mid
        if nums[end] == target:
            return end
        if nums[start] == target:
            return start
        return -1

c++版本

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return: An integer
     */
    int lastPosition(vector<int> &nums, int target) {
        // write your code here
        if (nums.empty()) {
            return -1;
        }
        int start = 0;
        int end = int(nums.size()) - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] <= target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[end] == target) {
            return end;
        }
        if (nums[start] == target) {
            return start;
        }
        return -1;
    }
};

int main() {
    Solution solution;
    int a[6] = {1,2,2,4,5,5};
    vector<int> nums(a, a + 6);
    int target = 2;
    cout << solution.lastPosition(nums, target);
    return 0;
}