Find First and Last Position of

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums==null) return null;
        return bs(nums,target);
    }
    private int[] bs(int[] nums,int t){
        int n=nums.length;
        int s=-1,e=-1;
        int l=0,r=n-1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(t<nums[m]){
                r=m-1; 
            }else if(t>nums[m]){
                l=m+1;
            }else{
                s=m;
                e=m;
                int tmp=bsRange(nums,t,l,m-1,true);
                s=tmp<0?s:tmp;
                tmp=bsRange(nums,t,m+1,r,false);
                e=tmp<0?e:tmp;
                return new int[]{s,e};
            }
        }
        return new int[]{s,e};
    }

    private int bsRange(int[] nums,int t,int l,int r,boolean f){
        int idx=-1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(t<nums[m]){
                r=m-1;
            }else if(t>nums[m]){
                l=m+1;
            }else{
                idx=m;
                if(f){
                    r=m-1;   
                }else{
                    l=m+1;
                }
            }
        }
        return idx;
    }
}

时间O(logn)
空间O(1)

既然要求logn时间那得是二分查找了，我的思路是先用二分法找到他在不在，在的话将他作为分割点，分成两个子数组，对这两个子数组进行二分查找，在找到等于时不返回，继续遍历直到结束，使用idx记录最后一个匹配的位置。令我没想到的是竟然打败了100%的人。标准答案是用一个方法查找左右，我个人理解先查在不在应该是可以剪枝的。