May I know Why I get a Time Exceed Limit error?


  • 0
    Z

    I got a time exceed limit error with a binary search algorithm. I am pretty sure my running time is O(logn), and I can't understand why exceeding time limit.
    and the result is:

    Submission Result: Time Limit Exceeded  More Details 
    Last executed input:
    2126753390
    1702766719
    

    And here is the code:

    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int low = 1;
            int high= n;
            int mid = (int)((long)low+(long)high)/2;
            int gue = guess(mid);
            while(gue!=0){
                if(guess(mid)==-1){
                    high=mid-1;
                    mid = (int)((long)low+(long)high)/2;
                    gue = guess(mid);
                }else{
                    low=mid+1;
                    mid = (int)((long)low+(long)high)/2;
                    gue = guess(mid);
                }
            }
            return mid;
        }
    }
    

    Thank you so much!


  • 1

    @Zhen_Lian (int)((long)low+(long)high)/2; can be the problem, though I couldn't run the test for the time being (the OJ is down again, so sorry).

    • First, normally to avoid overflow we use low+(high-low)/2 instead.

    • Second, (int) whose precedence is higher than / which results in overflow of (int)((long)low+(long)high) and then you get the wrong intermediate to do division.

    So if you just change your version to the following one to retrieve the middle, you will AC.

    • (int)(((long)low+(long)high)/2);

  • 0
    Z

    Thank you so much LHearen! That really works! Your suggestion is really helpful!!!


Log in to reply
 

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