[릿코드] 278번 : First Bad Version

leetcode.com/problems/first-bad-version/

First Bad Version - LeetCode

---

문제

마지막 상품이 품질 체크에 실패했다. 이전 버전에 기반해 새로 개발되기 때문에 실패한 버전 이후로 나온 모든 버전은 동작하지않는다. 

n개의 버전이 있다고 가정하고 첫번째 실패한 버전을 찾아라.

bool isBadVersion()이라는 실패한 버전인지 아닌지 확인 할 수 있는 api가 제공된다. api 호출을 최소화 하여 첫번째 실패한 버전을 찾는 함수를 구현하라.

 

어떻게 풀까

첫번째 실패한 버전을 찾기 위해 binary search를 사용한다.

 

먼저 모든 버전이 실패한 버전이라 가정하여,

가장 마지막인 n번째 실패한 버전을 right로 두고,

첫번째로 실패한 버전을 left로 초기화 한다.

 

mid 를 left + (right - left) / 2로 설정한다

-> 실패하는 버전들 중에 가운데 값을 mid로 둔다.

 

mid가 나쁜 버전이면 right를 mid로 설정하여 right에 실패한 버전을 저장한다.

성공한 버전이면 mid+ 1을 left로 설정한다.

 

이렇게 left를 리턴하면 첫번째 실패한 버전이 나오게 된다.

 

구현

 

/* 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 left = 1;
      int right = n;
      while (left < right) {
          int mid = left + (right - left) / 2;
          if (isBadVersion(mid)) {
              right = mid;
          } else {
              left = mid + 1;
          }
      }
      return left;
	}
}