My log(n) solution in java


  • -1
    X
    public class Solution {
    public int search(int[] A, int target) {
         int n=A.length;
            //find what the minimum num's  actuall  index  is 
         int index=-1;
         if(A[0]<A[n-1])
        	 index=0;
         else{
        	 for(int i=1;i<n;i++)
        		 if(A[i]<A[i-1]){
        			 index=i;
        			 break;
        		 }
         }
    	 return recur(A,0,n-1,target,index);  
    }
    
    /*binary search like the old using logical index,the difference is that transforming 
    the logical index to the actual index when compare whether the mid is equal the target
    */
    private static int recur(int[] A, int start, int end, int target, int index) {
    	// TODO Auto-generated method stub
    	if(start>end)
    		return -1;
    	int n=A.length;
    	int mid=(start+end)/2;
    	int mmid=covert(mid,index,n);
        if(A[mmid]==target)
        	return mmid;
        if(A[mmid]<target)
        	return recur(A,mid+1,end,target,index);
        else
        	return recur(A,start,mid-1,target,index);
    	
    }
    
       // covert  from  the logical index to the actual index 
    private static int covert(int target, int index, int n) {
    	// TODO Auto-generated method stub
    	return (target+index)%n;
    }
    

    }enter code here


  • 0
    W

    In your first method to find minimum number in the array, you actually used O(n) time so the overall algorithm would be O(n). Instead, you can use a binary search to find the minimum as well, refer to the question "find minimum in rotated sorted array"


  • 0
    X

    I ignored the way of finding the minimum number in the array and just focus on the key question. I made a mistake! Actually it can be improved by using binary search. Thank you for your suggestion!


Log in to reply
 

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