drop-of-water

문제 링크

조건

  • 1 <= bad <= n <= 2^31 - 1
  • bad version 이 후 version 들은 모두 bad version임

입력값

  • isBadVersion = 해당 숫자가 BadVersion인지 확인하는 함수 (true/false return함) - leetcode에서 제공되는 API
  • n = 버전의 갯수 [1,…,n] 로 사용된다고 생각하면됨

출력값

  • 버전 중에서 가장 작은 수를 가진 bad version 값

풀이과정

  • 일반 루프를 사용해봤는데 time limit exceeded 에러 발생 (n의 값이 20억이 넘기 떼문)
  • binary search를 사용해 20억번 확인할 것을 9번으로 줄임
  • 현재 위치의 값이 bad version인 경우 이 후 version 들은 모두 bad version 이기 때문에 찾는 범위를 왼쪽으로 이동
  • 현재 위치의 값이 bad version이 아닌 경우 이 전 version 중에는 bad version이 없기 때문에 찾는 범위를 오른쪽으로 이동

코드

var solution = function (isBadVersion) {
  return function (n) {
    let low = 1;
    let high = n;
    let result = 0;

    // 이진 탐색 시작
    while (low <= high) {
      let mid = Math.floor((high + low) / 2);
      let guess = mid;

      // 현재 위치의 값이 bad version인 경우
      if (isBadVersion(guess)) {
        // 이 후 version 들은 모두 bad version 이기 때문에 찾는 범위를 왼쪽으로 이동
        high = mid - 1;

        // result에 bad version 값을 저장
        result = guess;
      }
      // 현재 위치의 값이 bad version이 아닌 경우
      else {
        // 이 전 version 중에는 bad version이 없기 때문에 찾는 범위를 오른쪽으로 이동
        low = mid + 1;
      }
    }
    return result;
  };
};

😊