First Bad Version

278. First Bad Version

이전에 공부했던 "선형탐색과 이분탐색" 포스트는 👉 여기
정렬된 배열에서 절반씩 특정 값을 찾는 이분탐색으로 시간복잡도 O(log n)이다.

문제

처음으로 나온 bad version 찾는 문제이다. 이분탐색으로 절반씩 전체 배열을 검사하여 가장 처음으로 생긴 bad version을 찾는다.

테스트 케이스

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

Binary Search

실패

isBadVersion는 version인 number(integer)를 파라미터로 받아 boolean을 리턴한다. 처음엔 n까지 배열을 만들고 하나씩 isBadVersion 함수로 검사했다.

// 코드 중략
return Array.from({length: n}, (v, i) => i + 1).filter(el => isBadVersion(el))[0]

// 당연히 2126753390와 같은 테스트 케이스를 입력받았을 땐 메모리 초과

개선

// 참고했던 Binary Search 코드

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Binary Search(위 코드)에서는 left와 right로 배열의 처음과 끝을 가리킨다. 문제의 조건처럼 n까지 정렬된 배열일 때, 배열의 중간 값인 mid 값과 target을 비교하여 mid > target, 찾고 있는 값보다 mid 값이 클 때 left 포인터를 mid + 1 인덱스로 옮겨주는 식이다.

First bad version은 위 코드와는 달리 target을 찾으면 빠져나오는 것이 아니라 모든 배열을 검사하기 위해 while의 조건으로 right(badNum)에서 left(goodNum)을 빼서 1 이상일 때만 검사한다. (left와 right 사이의 숫자가 하나라도 있으면 First bad version일 수 있기 때문에 모든 배열을 검사해야 한다)
left 혹은 right 인덱스 포인터를 이동하는 조건으로 isBadVersion에 mid 값을 검사하여 Bad version이면 badNum 포인터를 옮기고, 그렇지 않으면 goodNum 포인터를 이동시킨다.

풀이가 쓸데없이 길어진 것 같다. 코드를 보면,

// 코드 중략
return function(n) {   
  let badNum = n;
  let goodNum = 0;

  while (badNum - goodNum > 1) {
    let halfNum = Math.floor((badNum + goodNum) / 2)
    if (isBadVersion(halfNum)) {
      badNum = halfNum
    } else {
      goodNum = halfNum
    }
  }
  return badNum
};

처음 코드는 O(n)으로 2126753390와 같은 테스트 케이스는 isBadVersion 함수를 2126753390번 실행하지만, 이분 탐색으로는 31번으로 O(log n)의 시간복잡도를 가진다.