Is this code ok?


  • 0
    T
    first step get minvalue index  then  common binary search ,so the complexity is ? 
    
        public int search(int[] A, int target) 
        	 {
    		if (A == null || A.length < 1 ) 
                {
                   return -1;
                }
    	        if (A.length==1)
                {
                     return A[0]==target? 0:-1;
                }
    	int minindex=findMinIndex(A);
    		int L=0,R=A.length-1; 
    	if(target<A[L])
                {
                  L=minindex;
                }
    		else
                {
                   R=minindex-1>=L? minindex-1:R;
                } 
    		while(L<R) //二分查找
                {
                int M=(L+R)/2;
                if(A[M]>target){R=M;}
                else if(A[M]<target){L=M+1;}
                else{L=M; break;}
                }
    		if(L==R){return A[L]==target? L:-1;}
    		 return L;
    	 }
        
         public int findMinIndex(int[] A)
        	 {
        		 int L = 0, R = A.length - 1;
        		   while (L < R && A[L] >= A[R])
        		   {
        		      int M = (L + R) / 2;
        		      if (A[M] > A[R]) {
        		         L = M + 1;
        		      } else if (A[M] < A[L]) {
        		         R = M;
        		      } else {   // A[L] == A[M] == A[R]
        		         L = L + 1;
        		      }
        		   }
        		   return L;
        	 }

  • 0

    Could you please format your code by selecting your code, and then clicking on the {} button?


  • 0
    C

    the complexity is still O(lg n), though the solution is not so elegant as the solutions using one step.


Log in to reply
 

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