Short C++ answer and minimize API calls


  • 23
    W
    class Solution {
    public:
        int firstBadVersion(int n) {
            int lower = 1, upper = n, mid;
            while(lower < upper) {
                mid = lower + (upper - lower) / 2;
                if(!isBadVersion(mid)) lower = mid + 1;   /* Only one call to API */
                else upper = mid;
            }
            return lower;   /* Because there will alway be a bad version, return lower here */
        }
    };

  • 0
    J

    If you meet the first bad version during the loop, you cannot return it immediately, but you have to finish the loop and do some unnecessary checks, thus unnecessarily costs some extra time.

    Here is my code, although it has two API calls in each loop, but it can return the answer immediately when finds it. I don't know which is better, cause the test sample is so small and I am no good at math..

    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    class Solution {
    public:
        int firstBadVersion(int n) {
    		int low = 1, high = n, mid;
    		while(low <= high){
    			mid = low + (high - low) / 2;
    			if(!isBadVersion(mid))
    				low = mid + 1;
    			else{
    				if(mid == 1 || !isBadVersion(mid - 1))
    					return mid;
    				else
    					high = mid - 1;
    			}
    		}
        }
    };

  • 0
    X

    @JulianWang12 l think u r right


  • 4

    @JulianWang12 The binary search complexity is O(logn). For example, n=1024, we only need to check 10 times. In your case, only when you find the target in 5 iterations(10 checks), you save something. The probability of stopping within 5 iterations is just 32 out of 1024, which is pretty small. In other words, you code will call more isBadVersion() in most cases.


  • 0
    Z

    why if I use

    int mid = (start+end)/2;
    

    got time exceed limit issue

    using

     mid = start +(end-start)/2 
    

    will pass


  • 0
    Z

    @zilan (start + end) can overflow the int range and it will give a garbage value which will be divided by 2. start + (end - start)/2 does not let that happen. Keeps everything in the int range.


Log in to reply
 

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