O(logN) [8ms] Easy to understand Java solution


  • 0

    Divide and Concur, Binary Search

    import java.util.Arrays;
    
    public class Solution {
    	private int[] nums;
    	private int target;
    	private int[] range = new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
    
    	public int[] searchRange(int[] nums, int target) {
    
    		if (nums.length == 0)
    			return new int[] { -1, -1 };
    
    		this.nums = nums;
    		this.target = target;
    
    		this.searchRange(0, nums.length - 1);
    		if (range[0] > range[1])
    			return new int[] { -1, -1 };
    		else
    			return range;
    	}
    
    	private void searchRange(int i, int j) {
    		if (i > j)
    			return;
    		int mid = i + (j - i) / 2;
    		if (nums[mid] > target) {
    			searchRange(i, mid - 1);
    		} else if (nums[mid] < target) {
    			searchRange(mid + 1, j);
    		} else {
    			searchRange(i, mid - 1);
    			searchRange(mid + 1, j);
    			range[0] = Math.min(range[0], mid);
    			range[1] = Math.max(range[1], mid);
    		}
    	}
    }

Log in to reply
 

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