Must note that the uniqueness condition is important !


  • 0
    T

    you should note that the condition that "all elements are unique " is important, otherwise you would have a situation like [ 0 1 -1 0 0 0 0 ], which could be considered a rotation of [ -1 0 0 0 0 0 1 ]. in this case if you just compare A[low] and A[mid] ( or, A[0] and A[3] ), the situation would be the same with [ 0 0 0 0 1 -1 0 ], which is also a legal rotation. but for example if u search for 1 in both cases, you should get different answers, but just comparing A[low], A[high], A[mid] would lead to completely the same answers, causing a mistake (at least when we are limited to log(N) algorithms, i.e. in fact to distinguish the above 2 situations you would have to resort to a linear scan of the input )

    btw here is my accepted solution

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

    }


  • 0
    T

    when I first saw this question in a real interview, I failed because I was so fixated on how to solve this when A[low] == A[high] or A[low] == A[mid], and disrupted my proof of the easier, "normal" input cases. so a take away from this is that you should always solve for the regular cases first, at least this would win you most of the score. edge cases can be always dealt with later


Log in to reply
 

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