LeetCode-34-在排序数组中查找元素的第一个和最后一个位置

题干

讲解

排序数组找一个值，自然而然就能想到二分查找；当然如果是直接循环也没问题，只不过时间复杂度是O(n)，不符合题干要求；
题干中我们可以看到他要求O(log n)的时间复杂度，所以用的方法就是二分查找；

这里分享一下y总的整数二分查找的模板

注意第二种方法是 (l+r+1)/2

题解

public static int[] searchRange(int[] nums, int target) {
    if(nums.length == 0){
        return new int[]{-1,-1};
    }
    int left = check_left(nums, target);
    int right = check_right(nums, target);

    if(nums[left] != target){
        return new int[]{-1, -1};
    }else{
        return new int[]{left, right};
    }

}

/**
 * 查找第一个出现的位置
 * @param nums
 * @param target
 * @return
 */
public static int check_left(int[] nums, int target){

    int left = 0;
    int right = nums.length-1;

    while(left < right){
        int temp = (left+right)/2;
        if(nums[temp]>=target){
            right = temp;
        }else{
            left = temp+1;
        }
    }

    return left;
}

/**
 * 查找最后一个出现的位置
 * @param nums
 * @param target
 * @return
  */
public static int check_right(int[] nums, int target){

    int left = 0;
    int right = nums.length-1;

    while(left < right){
        int temp = (left+right+1)/2;
        if(nums[temp]<=target){
            left = temp;
        }else{
            right = temp-1;
        }
    }

    return left;
}