The brute force solution is accepted.


  • 0
    F

    The brute force solution to this problem is accepted, since traversal the array is only o(n) time.


  • 0
    F

    The aim of this problem is finding solution using less time, say o(log n), isn't it?


  • 0
    L

    The aim of the problem is to find an algorithm running in O(log n) with a big O. That's the optimal solution. So o(log n) with a small o is not reachable.


  • 0
    F

    It was just a typo, I mean O(logn). My question is the brute force solution (O(n)) can be accepted.


  • 0
    L

    That does not sound like a question to me… But I agree, the judge accepts brute force algorithms here.


  • 5

    It is difficult to differentiate between O(n) and O(log n) algorithm in general, as @loick already answered nicely here. Since the O(n) algorithm traverses the array in sequence, it is extremely fast as the cache hit rate is going to be high.

    On the other hand, the O(log n) binary search algorithm has more unpredictable array index access, which means it will result in more cache misses.

    Unless n is extremely large (up to billions, which is unpractical in this case), there could be a chance that the Brute Force O(n) algorithm is actually faster.


  • -5
    G

    EDIT : Kindly ignore my comment, its incorrect!

    I don't think a solution better the O(n) is possible.

    To do binary search in the rotated array, one needs to find the pivot at which rotation takes place. After find the pivot, it is possible to do binary search in the two sorted arrays separately. But finding the pivot can be O(n) worst case -- say if the array was not rotated, implying no pivot element and then one would have to do a binary search in the whole array.


  • 0
    S

    No, there is a O( log N) way to find the pivot. So the best solution could be O(log N). The solution will degrade into O(n) only when there is duplicate elements in array.


  • 0
    G

    Can you tell me how to find the pivot element in O(log N)? I have thought about it but couldn't come up with a way of doing it. Thanks :)


  • 0

    Check this article, it may help you out.


  • 0
    G

    Differentiating between O(n) and O(n logn) is difficult because logn increases very slowly [As is mentioned in the reference link]. It as same as differentiating O(1) and O(logn) algorithms.
    However, O(n) and O(log n) algorithms can be easily differentiated. n~10^5 would be more than enough.


  • 0
    R

    My solution is log N.

    I have two nested recursive binary searches. The internal is a regular binary search.
    The top level one is an altered binary search (a pivot search) that does:

    • 1 check if the first element is the target, return if so.
    • 2 check if the first element is minor than the last, than we assume that everything in the middle is sorted. Then call binary search recursive function and return its result.
    • 3 split the section into two parts choosing a pivot in the middle.
    • 4 test the right half and return only if the target is found.
    • 5 test the left part and return its result.

    Point 2 is a variant on the traditional binary search and also the fact that we have to perform the search on both halves at points 4 and 5.

    Is logN but have two status:

    • recursive pivot search
    • recursive binary search

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

    }
    I used binary search here, comparing to common binary search method it adjust a little. When making the judgement which side to search, it differs in which side is ordered. Because a rotate array must be normally ordered in one side.


Log in to reply
 

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