My code shows correct answer on ideone on the same input but gives WA here. Ideone link : http://ideone.com/PQ1ZZl


  • 0
    P
    // Function to find the pivot
         int pivot_search(int A[],int low, int high)
        {
            if(low > high) return -1;
            
            int mid;
            mid = (low+high)/2;
            if(high-low+1 == 2 && A[low] > A[high]) return low; // If there are two elements then only low and high                    are to be compared
            if( A[mid-1] < A[mid] && A[mid+1] < A[mid]) return mid;
            
            if(A[mid] < A[low]){
                return pivot_search(A,low,mid-1);
            } else {
                return pivot_search(A,mid+1,high);
            }
        }
        //Simple binary search 
        int binary(int A[], int low, int high, int x)
        {
            if(low > high) return -1;
            int mid = (low+high)/2;
            
            if(A[mid] == x) return mid;
            
            if(A[mid] < x){
                return binary(A,mid+1, high,x);
            } else {
                return binary(A,low, mid-1, x);
            }
        }
        
        
        
        class Solution {
        public:
           int search(int A[], int n, int target) {
                
                int pivot;
                pivot = pivot_search(A,0,n-1); 
                if(pivot == -1) pivot = n-1; // if pivot is not found then it means the array is sorted so pivot is n-1.
             //  cout << pivot << endl;
                if(target >= A[0]){ // if target >= A[0] then search in array till the pivot
                    return binary(A,0,pivot,target);
                } else { // else search in the array after the pivot
                    return binary(A,pivot+1,n-1, target);
                }
        }
        };

  • 0
    S

    Could you please add words about your idea and comments in code? Thanks.


  • 0
    P

    I have added the proper comments! Please check the code! :)


  • 0
    S

    What is the test case? Could you please also add to question post? Thanks.


  • 0
    S

    I think your code do not handle edge case very well. Thinking about only 2 elements in array, the mid in your pivot search, will be 0, and mid-1 will out of range.


  • 0
    P

    It is running fine on two elements as well. check this link http://ideone.com/JsW1JT
    The test case it fails on (as shown by LEETCODE OJ) is [5,1,3], 1.. While this test case also runs fine on ideone.


  • 0
    S

    Have you ran this case by your hand on paper? What value of pivot will you get? Since mid-1 will out of range, cpp cannot promise anything. In such situation, you cannot over rely on running environment. That is the reason why you get right result on your local, but fail on OJ.


  • 0
    P

    Sir, You are missing a very important line of the code. In the function pivot_search() , there is a special case handled for two elements :
    if(high-low+1 == 2 && A[low] > A[high]) return low;

    So, there are no issues for this!


  • 0
    S

    For test case {5, 1, 3}, 1 , when the 1 level, low=0, high=2, mid=1, since A[mid] < A[low], ie 1 < 5, so the 2 level is low=0, high=0, then your code will hit this line if( A[mid-1] < A[mid] && A[mid+1] < A[mid]) return mid; I just run your code in my mind, maybe I get wrong.


Log in to reply
 

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