Leetcode 278. First Bad Version - Binary Search Tree

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        low = 1
        high = n
        while (low <= high):
            mid = (low + high) // 2
            if isBadVersion(mid): # isVersion(mid) -> true
                high = mid - 1
            else:
                low = mid + 1
        return low

10/2, 평소 코딩 연습을 하던 Leetcode에서, 매일 푸는 문제에서 이용되는 자료구조/알고리즘 이론을 기록하기로.

 

Number : 278

Problem : First Bad Version

Level : Easy

Algorithms : Binary Search Tree

 

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        for i in range(1, n+1):
            if isBadVersion(i):
                return i

처음에 이렇게 코드를 짰다.

Time Complexity : O(n)

Memory Complexity : O(1)

 

Binary Search Tree

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. (출처 : 나무위키)

 

수도코드  

binarySearch(A[0..N-1], value) {//k
  low = 0
  high = N - 1
  while (low <= high) {
      mid = (low + high) / 2
      if (A[mid] > value)
          high = mid - 1
      else if (A[mid] < value)
          low = mid + 1
      else
          return mid // found k
  }
  return -1 // not found k
}

Time Complexity : O(logn)

 

수도코드를 이용하여 완성하면

Accepted된다.

 

끝!

 

 

출처 : Leetcode, Wikipedia