Description

First Bad Version - LeetCode

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.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

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

Solution

• Related Topics에 바이너리 서치가 있어서 그렇게 풀었는데 효율이 개박살났다.
  • 찾는 값은 first bad version이므로 isBadVersion으로 체크했을 때 pivot은 false, pivot + 1은 true로 나와야한다고 생각했다.

public int firstBadVersion(int n) {
        if (isBadVersion(1)) return 1;
        
        int pivot, left = 1, right = n;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            if (isBadVersion(pivot)) right = pivot - 1;
            if (!isBadVersion(pivot)) {
                if (isBadVersion(pivot + 1)) {
                    return pivot + 1;
                }
                left = pivot + 1;
            }
        }
        return 0;
    }

• Solution 보고 작성한 코드

  • isBadVersion으로 체크했을 때 true와 false 값이 바뀌는 시점은 상관없이 left값을 first bad version에 놓이게 한다.

  • Binary Search에서 어떨 때는 pivot + 1을 하고 어떨 때는 pivot으로 left나 right 값을 잡아주는데 문제가 요하는 바를 이해하고 쓰는 게 먼저..

    https://leetcode.com/problems/search-insert-position/discuss/249092/Come-on-forget-the-binary-search-patterntemplate!-Try-understand-it

public int firstBadVersion2(int n) {
        int left = 1, right = n, pivot;
        while (left < right) {
            pivot = left + (right - left) / 2;
						
						// left 값이 first bad version으로 가는 게 목표이기 때문에 pivot + 1
            if (!isBadVersion(pivot)) left = pivot + 1;

            else right = pivot; // right 값이 left보다 적어질 수 있으므로 pivot
        }

        return left;
    }