Remember the Binary Search Goals.


  • 0

    So as a binary search, if you are aware of taking notes on the last_valid index or value, this pattern could solve a lot searching questions. As long as you nail down what is the last valid states you are looking for.

    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);
    
    class Solution {
    public:
        // find the last good version 看我出神入化的二分查找
        int search(int left, int right) {
            // assume the last good is version 0, so if the actually bad starts from version 1 (the beginning)
            // then the 0 will be the last good version number.
            int last_good = 0;
            
            while (left <= right) {
                int mid = left + (right - left) /2 ;
                if (isBadVersion(mid)) {
                    right = mid - 1;
                } else {
                    last_good = mid;
                    left = mid + 1;
                }
            }
            
            return last_good+1; // hah, +1 to become the first bad version.
        }
        
        int firstBadVersion(int n) {
            return search(1, n);
        }
    };
    

Log in to reply
 

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