458. Last Position of Target

做题历程：

1. 本题应该是第一次做，本次耗时6分钟，独立解出

本题其实跟14. First Position of Target基本一样，用同样的模板解题即可。。都是用Binary Search，代码如下：

class Solution {
public:
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    int lastPosition(vector<int>& A, int target) {
        // Write your code here
        if (A.empty()) {
            return -1;
        }
        int left = 0;
        int right = A.size() - 1;
        while (left + 1 < right) {
            int middle = (left + right) / 2;
            if (A[middle] < target) {
                 left = middle + 1;
            }
            else if (A[middle] == target) {
                left = middle;
            }
            else {
                right = middle - 1;
            }
        }
        if (A[right] == target) {
            return right;
        }
        if (A[left] == target) {
            return left;
        }
        return -1;
    }
};