23.02.21 Today’s Leetcode

540. Single Element in a Sorted Array (medium)

Binary Search의 업그레이드 버전.

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # exactly twice
        n = len(nums)
        def dfs(start, end):
            nonlocal nums
            if start >= end:
                return nums[end]
            mid = (start + end) // 2
            if mid < n and nums[mid] == nums[mid - 1]:
                if (mid - 1 - start) % 2 == 1:
                    return dfs(start, mid)
                else:
                    return dfs(mid + 1, end)
            if mid + 1 < n and nums[mid] == nums[mid + 1]:
                if (mid - start) % 2 == 1:
                    return dfs(start, mid)
                else:
                    return dfs(mid + 2, end)
            return nums[mid]
        
        return dfs(0, len(nums))

704. Binary Search (easy)

정석적인 Binary Search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums)
        while start < end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid + 1
            elif nums[mid] > target:
                end = mid
            else:
                return mid
        if start < len(nums) and nums[start] == target:
            return start
        return -1

278. First Bad Version (easy)

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        start, end = 0, n
        while start < end:
            mid = (start + end) // 2
            if not isBadVersion(mid):
                start = mid + 1
            else:
                end = mid
        return start