Last Position of Target

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

来源： http://www.lintcode.com/en/problem/first-position-of-target/

分析

找排序数组某个数字的右边界

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 left = 0, right = nums.length -1, mid;
        while(left < right){
            mid = left + (right - left + 1) / 2;//insure when right is 1 bigger than left, mid eaqual to right                        
            if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid;
            }
        }
        if(nums[right] == target)
            return right;
        else
            return -1;
    }
}

null