Java Easy to understand O(lg n) solution


  • 1
    N
    private int binarySearch(int[] A, int target) {
    		if(A.length == 0)
    			return -1;
    		int right = A.length - 1;
    		int left = 0;
    		while(left<=right) {
    			int middle = left + (right-left)/2;
    			if(target > A[middle])
    				left = middle + 1;
    			else if(target < A[middle])
    				right = middle - 1;
    			else 
    				return middle;
    		}
    		return -1;
    	}
    	private int leftMost(int[] A, int left, int right, int target){
    		while(left <= right) {
    			int middle = left + (right - left)/2;
    			if(target == A[middle]) {
    				if(middle != 0 && A[middle] == A[middle - 1])
    					right = middle - 1;
    				else {
    					return middle;
    				}
    			} else {
    				left = middle + 1;
    			}
    		}
    		return -1;
    	}
    	
    	private int rightMost(int[] A, int left, int right, int target) {
    		while(left <= right) {
    			int middle = left + (right - left)/2;
    			if(target == A[middle]){
    				if(middle != (A.length - 1) && A[middle] == A[middle + 1])
    					left = middle + 1;
    				else { 
    					return middle;
    				}
    			} else {
    				right = middle - 1;
    			}
    		}
    		return -1;
    	}
    	public int[] searchRange(int[] A, int target) {
    		int anchor = binarySearch(A, target);
    		int left = -1;
    		int right = -1;
    		if(anchor != -1) {
    			left = anchor;
    			right = anchor;
    			System.out.println("anchor is: "+anchor);
    			if(anchor != 0 && A[anchor] == A[anchor -1]) {
    				//lets find the left most index
    				left = leftMost(A, 0, anchor - 1, target);
    			} 
    			if(anchor != (A.length-1) && A[anchor] == A[anchor+1]) {
    				//lets find the right most index
    				right = rightMost(A, anchor + 1, A.length - 1, target);
    			}
    		}
    		return new int[] {left, right};
    
    	}

Log in to reply
 

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