Reference

• leet code 278 : first bad version

1. 문제 설명

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

• isBadVersion() 메서드를 최소한으로 호출하여 n개의 제품 중 첫번째로 생성된 잘못된 버전을 찾는 것이 핵심인 것 같습니다.

---

접근 방법

a) 첫 번째 접근

• 우선 n개의 제품을 탐색하면서 메서드 호출 횟수를 최소화 하기 위해서 O(log n)의 시간복잡도를 사용합니다.
• 그 이유는 O(log n)이 탐색 시간 복잡도 중 최소 값이기 때문입니다.
• 그러므로 이진 탐색을 사용하면서 동시에 two pointers 방법을 사용하여 탐색 효율을 최대화 합니다.

b) 두 번째 접근

• 문제의 제약에 따르면 제품은 1번부터 시작입니다.
• 그러므로 two pointers를 설정할 때, 시작(= start) index는 1번이 됩니다.
• 마지막(= end) index는 제품의 개수(= n)와 동일합니다.

c) 세 번째 접근

• 중간(= mid) index를 계산합니다.

• 중간 index를 계산하는 공식은 다음과 같습니다.
  → start + (end - start) / 2

• mid를 계산하는 과정에서 (end - start) / 2는 알아두면 좋은 트릭이자 노하우라고 합니다.

• (end - start)를 수행하는 이유는 mid를 계산할 때 n의 표현 범위를 초과하지 않기 위해서입니다.

• 1 <= bad <= n <= 231 - 1

• 문제의 제약을 보면 n(= 제품의 수)의 최대 표현값이 int 자료형의 최대 표현값과 동일합니다.

• 만약 end의 값이 최대 값이고 mid를 (start + end) / 2로 계산하는 경우, 오버플로우가 발생하므로

• 제약조건에 따른 자료형의 오버플로우를 방지하기 위한 트릭으로 (end - start)를 사용한다고 합니다.

• 제약조건이 있든 없든, mid를 계산할 때 "start + (end - start) / 2"라는 공식을 사용하는 것이 권장됩니다.

d) 네 번째 접근

• isBadVersion(mid)의 반환 값이 true인 경우, 해당 버전 이전의 제품 중 최초의 잘못된 제품이 존재한다는 의미이므로
• end는 mid가 되고, 다시 탐색을 시작합니다.
• 탐색을 계속하는 조건은 start가 end보다 작은 경우일 때까지 입니다.
• 즉, start == end가 되는 경우가 최초의 잘못된 제품을 가리키는 것입니다.

---

구현

/* 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;
        
        while(start<end) {
            int mid = start+(end-start)/2;
            // 현재 버전이 잘못된 경우
            if(isBadVersion(mid)) {
            // 이분 탐색
                end = mid;
            }
            // 올바른 경우
            else {
                start = mid+1;
            }
        }
        return start;
    }
}