Getting TLE for O(logn) code


#1

Getting TLE even though the code seems to be working in O(logn) time. First finding pivot in O(logn) and then finding the target also in O(logn). Can’t seem to figure out where the problem lies.

public class Solution 
{
    // DO NOT MODIFY THE LIST
    public int search(final List<Integer> a, int b) 
    {
        int start = 0, end = a.size() - 1, mid;
        int n = a.size();
        int pivot = 0;
        
        while(start<=end)
        {
            if(a.get(start)<=a.get(end))
                pivot = start;
            
            mid = (start+end)/2;
            int next = (mid+1)%a.size(), prev = (mid+a.size()-1)%a.size();
            if(a.get(mid)<=a.get(next) && a.get(mid)<=a.get(prev))
                pivot = mid;
            else if(a.get(mid)<=a.get(end))
                end = mid - 1;
            else
                start = mid + 1;
        }
        
        start = 0; end = a.size() - 1;
        if(b<=a.get((pivot+n-1)%n))
        {
            start = 0;
            end = (pivot+n-1)%n;
        }
        else if(b>=a.get(pivot))
        {
            start = (pivot+1)%n;
            end = n - 1;
        }
            
        while(start<=end)
        {
            mid = (start+end)/2;
            
            if(a.get(mid)==b)
                return mid;
            else if(a.get(mid)>b)
                end = mid - 1;
            else
                start = mid + 1;
        }
        
        return -1;
    }
}

#2

same thing happening with me.


#4

in the first while loop(to find the pivot), in the if condition where you are checking that both the next and previous element should be greater than the mid value, you’ve just assigned the pivot to mid and no break statement or anything. So, high and low will remain the same and the loop will keep running endlessly


#5

we may need not to find pivot element, we need to categorically use binary search.
for me this simple conditional block works.
// b lies in start to mid
if((start < midel && (b > start && b < midel)) || ((start > midel) && (b > start || b < midel))){
en = mid - 1;
}else {
//if((midel < end && (b > midel && b < end)) || ((midel > end) && (b > midel || b < end))){
// b lies in mid to en
st = mid + 1;
}


#6

The reason may be because the code will run into an infinite loop if the input is not rotated. I faced the same problem. This code may work only for sorted and rotated array