Can you tell me why I was WA?


  • 0
    T

    At first, please excuse my poor English.

    The following is my solution about Search in Rotated Sorted Array, the OJ told me I was wrong and the detail is when input data is [3,1], my solution's output is -1. But what I really unbelievable is actually when the input data is [3,1], my solution's output is 1, and it seems doesn't matter.

    class Solution {
    public:
        int findPivot(vector<int> &nums,int low,int high){
            if(low>high){
                return -1;
            }
            int mid=(low+high)/2;
            if(nums[mid]>=nums[low]){
                int tmpPivot=findPivot(nums,mid+1,high);
                return nums[tmpPivot]<=nums[low]?tmpPivot:low;
            }else if(nums[mid]<nums[low]){
                int tmpPivot=findPivot(nums,low,mid-1);
                return nums[mid]<=nums[tmpPivot]?mid:tmpPivot;
            }
            return -1;
        }
    
        int BinarySearch(vector<int> &nums,int low,int high,int target){
            if(low>high){
                return -1;
            }
            while(low<=high){
                int mid=(low+high)/2;
                if(nums[mid]==target){
                    return mid;
                }
                if(nums[mid]<target){
                    low=mid+1;
                }
                if(target<nums[mid]){
                    high=mid-1;
                }
            }
            return -1;
        }
    
        int search(vector<int>& nums, int target) {
            if(nums.size()==0){
                return -1;
            }
            int pivot=findPivot(nums,0,nums.size()-1);
            int index=BinarySearch(nums,0,pivot-1,target);
            if(index!=-1){
                return index;
            }
            return BinarySearch(nums,pivot,nums.size()-1,target);
        }
    };
    

    So can you tell me the reason? Thanks for your help!


Log in to reply
 

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