Last Position of Target

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.

Notes:

1. Last position means that can't stop when find it, continue to find the last one (start == middle)

    public int lastPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length-1;
        while(start+1 < end) {
            int middle = start + (end-start)/2;

            if (nums[middle] <= target) {
                start = middle;
            } else {
                end = middle;
            }
        }

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

        if (nums[start] == target) {
            return start;
        }

        return -1;
    }