[LeetCode] 278. First Bad Version - 문제풀이

Description

버전을 명시하는 정렬된 int 배열에서 특정 버전 이후는 모두 badVersion 을 나타내고 있을때 첫번째 badVersion을 나타내는 요소를 찾는 문제입니다.

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 <= 2^31 - 1

Solution 1. 이진 탐색(Binary Search)

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-1;
        }else{
            start = mid+1;
        }
    }
    return start;
}

정렬되어 있는 배열에서 원하는 값을 찾기 위해 이진 탐색(Binary Search)을 이용할 수 있습니다.

검색 범위를 지정할 두개의 포인터를 두고 가운데 값(mid)을 스캔한 후 찾는 값(target)이 중간값보다 작으면 스캔범위를 포인터를 앞으로 옮기고 아니면 뒤쪽을 스캔하는 것을 반복합니다.

• 시간복잡도 : O(logN)
• 공간복잡도 : O(1)

Reference

First Bad Version - LeetCode