My iterative 364ms Java solution


  • -1
    J

    See below:

    public int[] searchRange(int[] nums, int target) {
    	int[] range = {-1, -1};
    
    	if (nums == null || nums.length == 0)
    		return range;
    
    	int low = 0;
    	int high = nums.length - 1;
    	int mid = 0;
    	boolean flag = false;
    	while (low <= high) {
    		mid = (low + high) / 2;
    		if (nums[mid] == target) {
    			flag = true;
    			break;
    		} else if (nums[mid] > target) {
    			high = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    	if (!flag)
    		return range;
    
    	range[0] = mid;
    	range[1] = mid;
    	int temphigh = high;
    	int tempmid = mid;
    
    	high = mid - 1;	// search for the low end
    	while (low <= high) {
    		mid = (low + high) / 2;
    		if (nums[mid] == target) {
    			range[0] = mid;
    			high = mid - 1;
    		} else if (nums[mid] > target) {
    			high = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    
    	high = temphigh;
    	mid = tempmid;
    
    	low = mid + 1;	// search for the high end
    	while (low <= high) {
    		mid = (low + high) / 2;
    		if (nums[mid] == target) {
    			range[1] = mid;
    			low = mid + 1;
    		} else if (nums[mid] > target) {
    			high = mid - 1;
    		} else {
    			low = mid + 1;
    		}
    	}
    	return range;		
    }

Log in to reply
 

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