Last Position of Target

Last Position of Target.png

===================== 解題思路 =====================

跟 first position of target 相同的題目 只是這次在 mid index 內容 = target 時 移動的是 left 的 index (left = mid)

===================== C++ code ====================

<pre><code>
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.size() == 0) return -1;
    int left = 0, right = A.size() -1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(A[mid] <= target) left = mid;
        else right = mid;
    }
    if(A[right] == target) return right;
    if(A[left] == target) return left;
    return -1;
}

};
<code><pre>