[이진탐색][JavaScript][LeetCode] #278. First Bad Version

#이진탐색  #EASY

First Bad Version - LeetCode

🌷 문제 설명

✏️ LeetCode 연습문제: First Bad Version
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.

🎃 제한 사항
1 <= bad <= n <= 231 - 1

입출력 예

n	bad	result
5	4	4
1	1	1

 

🌷 내 코드

1. while문 사용하여 구현

var solution = function (isBadVersion) {
  return function (n) {
    let start = 0;
    let end = n; // Bad
    while (start + 1 < end) { // 이거 때문에..! start < end 아니라 start+1
      let mid = Math.floor((start + end) / 2);
      if (isBadVersion(mid)) {
        end = mid; // true면 왼쪽 확인. 전엔 인덱스였기 때문에 +1 해줬으나 여기선 필요 없음
      } else {
        start = mid; // false면 오른쪽 확인
      }
    }
    return end;
  };
};

2. 재귀 사용하여 구현

var solution = function (isBadVersion) {
  // 이진 탐색 할 재귀함수 새로 설정
  const recursion = (start, end) => {
    if (isBadVersion(start) && isBadVersion(end)) return start;
    const mid = Math.floor((start + end) / 2);
    if (isBadVersion(mid)) return recursion(start + 1, mid); // 맞으면 왼쪽 확인
    else return recursion(mid + 1, end); // 틀리면 오른쪽 확인
  };

  return function (n) {
    return recursion(1, n);
  };
};

 

🌷 코멘트

- 똑같은 코드를 타입스크립트로 썼을 때 이 전 문제에선 메모리를 절약하더니 여기선 썩 그렇지도 않았다. 일단 느린건 확실한듯!
- 머릿속으로 코드를 돌려봐도 이상한 점이 없는데 자꾸 테케를 통과하지 못해서 답답했는데 범위를 잘못 설정했었다. 근데 지금 보니 내 코드처럼 쓰는것 보다는 end-start > 1 로 범위 설정하는게 더 코드 가독성이 좋을 것 같다.
- 홀리몰리 과카몰리 재귀 사용해서 쓰니까 겁나 빨라짐! 왜.. 왜지? 원래 더 느려야되는거 아닌가? 이유는 다음에 알아보자..

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview