Simple Java Binary Solution With Explanation


  • 0
    M

    You might be thinking where to stop. Here we are not searching for a particular number or item. So the binary search needs to go to the worst case which is O(logn) because it is at that point that the correct index of first bad version will be returned.

    public int firstBadVersion(int n) {
            return firstBadVersionUtil(1, n);
        }
        
        private int firstBadVersionUtil(int low, int high) {
            
            if (low > high) return low;
            
            int mid = low + ((high - low) / 2);
            if (isBadVersion(mid)) {
                return firstBadVersionUtil(low, mid - 1);
            } else {
                return firstBadVersionUtil(mid + 1, high);
            }
        }
    

Log in to reply
 

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