My java solution with explanation


  • 0
    G

    The idea is basic binary search with some tricky points to think of.
    Since the array is rotated, we have to make sure which part we are in right now. The order is ascending order, so we compare with the right one to decide.

    Two cases:

    A1= [4,5,6,7,8,9,1,2,3];
    A2= [9,1,2,3,4,5,6,7,8];

    In A1, l=4, r=3, m=8, A[m]>A[r], we can know A[l] to A[m] is in ascending order.

    In A2, l=9, r=8, m=4, A[r]>A[m], we can know A[m] to A[r] is in ascending order.

    After this, we compare the target with the two boundary elements of the ascending ordered part, see if the target lie in it. If not so, we choose from the other part.

    Note that in BST, if we give while(left<=right), we have to make sure, right=mid-1, and left=mid+1, so that every element will be reached.

     public class Solution {
        public int search(int[] A, int target) {
            if(A==null || A.length==0)
                return -1;
            int l = 0;
            int r = A.length-1;
            while(l<=r)
            {
                int m = (l+r)/2;
                if(target == A[m])
                    return m;
                if(A[m]<A[r]){
                    if(target>A[m] && target<=A[r])
                        l = m+1;
                    else
                        r = m-1;
                }
                else{
                    if(target>=A[l] && target<A[m])
                        r = m-1;
                    else
                        l = m+1;                    
                }
            }
            return -1;
    
        }
    }
    

    Get the idea from here.


Log in to reply
 

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