Search-in-rotated-sorted-array,why such simple answer is accepted


  • -1
    S

    such simple answer is accepted, i think more complex input should be added to the case

    class Solution {
    
    public:
        int search(int A[], int n, int target) {
    
            for(int i=0;i<n;i++){
                if(A[i]==target){
                    return i;
                }
            }
            return -1;
    
    
        }
    };

  • 0
    C

    That's OK, it can get the right output, but not the most effective,

    Check mine:

    class Solution {
    public:
        int search(int A[], int n, int target) {
            
            int ret;
    
            ret = searchcirle(A,0,n-1,target);
            return ret;
        }
        
        int searchcirle(int A[],int i, int j, int target) {
            
            int k,ret;
            
            if(i > j) return -1;
            if(i==j && A[i]==target) return i;
            if(i==j && A[i]!= target) return -1;
            
            k=(i+j)/2;
            
            if(A[k] == target) return k;
            ret = searchcirle(A,i,k-1,target);
            if(ret != -1) return ret;
            
            ret = searchcirle(A,k+1,j,target);
            if(ret !=-1) return ret;
            
            return -1;
        }
    };

  • 0
    S

    hi, in my understanding, complexity of your solution is also O(n), seems not most effective.


  • 0
    S

    The OJ might accept this solution but in an interview setup for this question, when you give a O(n) solution the interviewer would direct you to optimize or indirectly calling for a binary search solution. Thats the reason why this problem is graded as hard in OJ as it involves checking for various bounds using binary search. Hope this helps !


  • 0
    M
    class Solution:
        # @param A, a list of integers
        # @param target, an integer to be searched
        # @return an integer
        def search(self, A, target):
            if target in A :
                return A.index(target)
            else:
                return -1
    

    True ! OJ accepts the above solution in python ( which pretty much defeats the purpose of the exercise) . I m working on an updated solution - but it pretty much depends on the users to not use such short cuts and train properly.


Log in to reply
 

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