Page tree
Skip to end of metadata
Go to start of metadata

Runtime: 74.06%

First Bad Version
class Solution:
    def firstBadVersion(self, n):        
        """
        :type n: int
        :rtype: int
        """
        cur = int(n / 2)
        before = n
        
        if not isBadVersion(n-1) and isBadVersion(n): 
            return n
        
        while isBadVersion(cur-1) or not isBadVersion(cur):
            if isBadVersion(cur):
                before = cur                
                cur = int(cur / 2)
            else:
                cur = int((before + cur) / 2)
            
        return cur

Runtime: 90.25%, Memory Usage: 100%

Find First and Last Position of Element in Sorted Array
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        cur = int(length/2)
        last = length
        
        if length == 0: return [-1, -1]

        while nums[cur] != target:
            if nums[cur] > target:
                last = cur
                cur = int(cur / 2)
            elif nums[cur] < target:
                cur = int((last + cur) / 2)

            if cur == 0 and nums[cur] > target:
                return [-1, -1]

            if cur == length-1 and nums[cur] < target:
                return [-1, -1]

            if nums[cur] < target and nums[cur+1] > target:
                return [-1, -1]

        start = cur
        while (start - 1) >= 0 and nums[start-1] == target:
            start -= 1

        end = cur
        while (end + 1) < length and nums[end+1] == target:
            end += 1

        return [start, end]
  • No labels