Simple and Straight Forward C++ Solution with Explanation (7ms)


  • 1
    K

    This solution is based on the basic Binary Search. We only need to consider two added situations that are generated by rotation.

    class Solution {
    public:
        int search(int A[], int n, int target) {
            return helper(0,n-1,A,target);
        }
        //Basic Binary Search with considering two added situations because of rotation.
        int helper(int start, int end, int A[], int target){
            int mid=(start+end)/2;  
            if(A[mid]==target) return mid;
            if(start>=end) return -1;
            if(target<A[mid]){
                //consider the situation when part of the values that less than A[mid] was rotated to the right.
                if(A[mid]>A[end]&&target<A[start]) return helper(mid+1, end, A, target); 
                else return helper(start, mid-1, A, target);
            }
            else{
                //consider the situation when part of the values that larger than A[mid] was rotated to the left.
                if(A[mid]<A[start]&&target>A[end]) return helper(start, mid-1, A, target);
                else return helper(mid+1, end, A, target);
            }
        }
    };

  • 0
    T

    are you sure that your code has been accepted??


  • 0
    K

    I checked again. I am pretty sure there is no problem with the code. OA changed the input parameters of Search Function from array to vector. The only thing you need to pay attention is to change the parameters accordingly. (I changed the code and tested, it works.)


Log in to reply
 

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