My Java solution


  • 0
    J
    public class Solution {
    	public static int binarySearch(int[] A,int target){
    		int low = 0;
    	    int high = A.length - 1;
    	 
    	    while ((low <= high) && (low <= A.length - 1)
    	            && (high <= A.length - 1)) {
    	        int mid = (low+high)/2;
    	        if (target == A[mid]) {
    	            return mid;
    	        } else if (target < A[mid]) {
    	            high = mid - 1;
    	        } else {
    	            low = mid + 1;
    	        }
    	    }
    	    return -1;
    	}
    	public static int[] searchRange(int[] A, int target){
    		int[] range=new int[2];
    		if(binarySearch(A,target)==-1){
    			range[0]=-1;
    			range[1]=-1;
    		}else{
    			for(int i=binarySearch(A,target);i<A.length;i++){
    				if (A[i]==target){
    					range[1]=i;
    				}
    			}
    			for(int j=binarySearch(A,target);j>-1;j--){
    				if(A[j]==target){
    					range[0]=j;
    				}
    			}
    		}
    		return range;
    	}
    	public static void main(String[] args){
    		int [] A=new int[]{1,1,2};
    		System.out.println(binarySearch(A,1));
    		System.out.println(searchRange(A,1)[0]+" "+searchRange(A,1)[1]);
    	}
    }
    

    Use the binary search to find the position of target and find the duplicated number in the array.


Log in to reply
 

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