[LeetCode/easy/BinarySearch] First Bad Version

 

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

First Bad Version - LeetCode

 

각 버전은 이전 버전에 기반해서 디벨롭되고 bad 버전 이후의 모든 버전은 모두 bad 하다.

n개의 버전이 주어지고 첫 번째 bad 버전을 찾고 싶다. 

버전이 bad 했는지 아닌지 반환하는 API bool isBadVersion(version)이 주어지고 최소로 이 API를 호출해야 한다.

 

int firstBadVersion(int n) {
    int l=1, r=n;
    while(l<=r){
        int m = l+(r-l)/2;
        if(isBadVersion(m)) r = m-1;
        else                l = m+1;
    }
    return l;
}

 

---

 

int m = (l + r) / 2;       //1
int m = l + (r - l) / 2;   //2

이 부분이 왜 1번이 아니라 2번으로 했을까? 는 아래 글을 확인하자~

https://nyeoungkm.tistory.com/entry/알고리즘이분탐색BinarySearch-왜-leftright-left2는-overflow가-발생하지-않을까

[알고리즘/이분탐색/BinarySearch] 왜 left+(right-left)/2는 overflow가 발생하지 않을까?