278. First Bad Version java

https://leetcode.com/problems/first-bad-version/?envType=study-plan&id=algorithm-i 

First Bad Version - LeetCode

 

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {

        int start = 1;
        int end = n;
        int ans = -1;

        while (start <= end) {

            int mid = (start + end) / 2;
            
            if (isBadVersion(mid)) {
                end = mid - 1;
                ans = mid;
            } else {
                start = mid + 1;
            }
        }

        return ans;
        
    }
}

[ Time Limit Exceeded ]

이유를 찾아보니, overflow 이슈 때문이었다.

start + end가 Python이 아니면 overflow가 될 수 있기때문에

mid = (start + end) / 2가 아닌, start + (end - start)/2로 해주어야 성공할 수 있었다.

 

그래서 최종 성공코드는 아래와 같다.

 

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {

        int start = 1;
        int end = n;
        int ans = -1;

        while (start <= end) {

            int mid = start + (end - start) / 2;
            
            if (isBadVersion(mid)) {
                end = mid - 1;
                ans = mid;
            } else {
                start = mid + 1;
            }
        }

        return ans;
        
    }
}