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

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

For target =2, return 2.

For target =5, return 5.

For target =6, return -1.

Related problems

Closest Number in Sorted Arrary

Classical Binary Search

First Position of Target

Implementation

Link: http://lintcode.com/en/problem/last-position-of-target/

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 middle = left + (right - left) / 2;
            if(A[middle] > target) {
                right = middle;
            } else if(A[middle] == target) {
                left = middle;
            } else {
                left = middle;
            }
        }

        if(A[right] == target) {
            return right;
        } else if(A[left] == target) {
            return left;
        } else {
            return -1;
        }
    }
};