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.

分析

找排序数组某个数字的右边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

上一篇:使用echarts,制作色温图


下一篇:spring boot +mysql + mybatis + druid的整理(一)——单数据源