AUG!!! 0ms, beat 70%, O(log n), JAVA BS, basic and prunning.


  • 0
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
                    int[] result = {-1, -1};
    		if(nums == null || nums.length < 1)
        		return result;
    
    		return searchRangeHelper(nums,0, nums.length - 1, target, true, true);
        }
    	public int[] searchRangeHelper(int[] nums, int start, int end, int target, boolean searchLeft, boolean searchRight)
    	{
    	        int[] result = {-1, -1};
    		int left = start;
    		int right = end;
    		int mid = 0;
    // Step 1, we need to find at least one value in range [left, right] equals to target
    		while(left <= right)
    		{
    			mid = (left + right) / 2;
    			if(nums[mid] == target)
    			{
    // Step2, if we find that number and searchLeft is true, we need to keep search 
    //range [left, mid-1] to find if there exists a even lefter bond.
    //meanwhile set searchRight to false because we do not need to find a right bond
    // in the next search
    				if(mid > left && searchLeft)
    				{
    					int[] leftRes = searchRangeHelper(nums,start, mid - 1, target, true, false);
    					result[0] = leftRes[0] == -1? mid:leftRes[0];
    				}
    				else
    					result[0] = mid;
    //Step3, just like step 2, we need to find the biggest right bond.
    				if(mid < right && searchRight)
    				{
    					int[] rightRes = searchRangeHelper(nums,mid + 1, end, target, false, true);
    					result[1] = rightRes[1] == -1? mid:rightRes[1];
    				}
    				else
    					result[1] = mid;
    				
    				return result;
    			}
    			else
    			{
    				if(nums[mid] < target)
    					left = mid + 1;
    				else
    					right = mid - 1;
    			}
    		}
    		return result;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.