Why my code exceeds time limit, although used binary search


  • 0
    V
    /* The isBadVersion API is defined in the parent class VersionControl.
          boolean isBadVersion(int version); */
    
    public class Solution extends VersionControl {
      /*  public int firstBadVersion(int n) {
            if(!isBadVersion(n)) {
                return n;
            } else {
                return firstBadVersion(n-1);
            }
        }*/
        
      /*  public int firstBadVersion(int n) {
           while(isBadVersion(n)) {
               n -= 1;
           }
           
           return n;
        }*/
        
        public int firstBadVersion(int n) {
            
            
                if(isBadVersion(n) == true && isBadVersion(n-1) != true ){
                return n;
                }
                else if(isBadVersion(n/2)) {
                  return  search(1, n/2);
                } else {
                   return search(n/2,n);
                }
          
        }
        //checking in first half or second half
        public int search(int first, int last) {
            int mid =0;
            
            while(first <= last) {
                mid = (first+last) /2;
                if(isBadVersion(mid)) {
                    if(!isBadVersion(mid -1)) {
                        return mid;
                    } else {
                        last = mid -1;
                    }
                } else {
                    first = mid +1;
                }
                   
            }
            return first;
           
        }
    }

  • 0
    E

    I have the same error. If using mid = first+ (last-first) /2 then everything is ok.


  • 0

    Could you explain the difference between s+e/2 and s+(e-s)/2?


  • 0
    W

    It's strange, I meet the same problem, and I solved by using mid = first+ (last-first) /2


  • 2
    L

    The reason is that (first + last) may be larger than MAX_INT.


  • 0

    @liismn Thanks


Log in to reply
 

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