65、二分-在排序数组中查找元素的第一个和最后一个位置

思路： 

寻找数组中的目标值第一个和最后一个，如果不存在哪儿就是返回-1。

第一种方式直接线性遍历，找到目标值记录当前下标。继续寻找下一个不等于目标值，说明下一个目标值的下标就是结尾。直接返回。

第二种方式通过使用二分法寻找，先二分寻找寻找第一个目标值，如果存在再继续寻找最后一个目标值。代码如下：

class Solution {
     public static int[] searchRange(int[] nums, int target) {
        int[] ans = {-1, -1};
        if (nums==null||nums.length==0){
            return ans;
        }
        ans[0]=findFirst(nums,0,nums.length-1,target);
        if (ans[0]!=-1){
            ans[1]=findLast(nums,ans[0],nums.length-1,target);
        }
        return ans;
    }

    private static int findLast(int[] nums, int L, int R, int target) {
        if (nums[L]>target||nums[R]<target){
            return -1;
        }
        if (L==R){
            return target==nums[L]?L:-1;
        }
        int mid=R-(R-L)/2;
        if (nums[mid]<=target&&nums[R]>=target){
            return findLast(nums,mid,R,target);
        }else {
            return findLast(nums,L,mid-1,target);
        }
    }

    private static int findFirst(int[] nums, int L, int R, int target) {
        if (nums[L]>target||nums[R]<target){
            return -1;
        }
        if (L==R){
            return target==nums[L]?L:-1;
        }
        int mid=L+(R-L)/2;
        if (nums[L]<=target&&nums[mid]>=target){
            return findFirst(nums,L,mid,target);
        }else {
            return findFirst(nums,mid+1,R,target);
        }
    }
}