边界系列

• Input是标准的 Sorted Array（单调增或者单调减）
  • First or Last of Occrance!
  • 大于等于，小于等于，大于，小于，等于
• 每次淘汰的空间要确定是不属于结果范围的！

278. First Bad Version

• 000000011111111
• Find The First Occrance of an Element
  • 找的元素在不在数组里？while start < end 还是 while start < = end
  • How about Last Good Version?

# 写法1. 这种写法条件是target存在，且start = mid + 1
class Solution(object):
    def firstBadVersion(self, n):
        start, end = 1, n
        while start < end:
            mid = start + (end - start) / 2
            ret = isBadVersion(mid)
            if ret:
                end = mid
            else:
                start = mid + 1
        return start

# 写法2. 九章算法模板 - 预留两位做post processing
class Solution(object):
    def firstBadVersion(self, n):
        start, end = 1, n

        # 预留两位最后处理
        while start + 1 < end:
            mid = start + (end - start) / 2
            ret = isBadVersion(mid)
            if ret:
                end = mid
            else:
                start = mid + 1

        # Post Processing
        if isBadVersion(start):
            return start
        else:
            return end

35. Search Insert Position

• 找 > = target 的 first occrence

class Solution(object):
    def searchInsert(self, nums, target):
        if not nums: 
            return 0
        if target > nums[-1]:
            return len(nums)

        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] >= target:
                end = mid
            else:
                start = mid + 1

        # Post Precessing
        if nums[start] >= target:
            return start
        else:
            return end

34. Search for a Range

class Solution(object):
    def searchRange(self, nums, target):
        if not nums:
            return [-1, -1]

        # First Occurance
        start, end = 0 , len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] >= target:
                end = mid
            else:
                start = mid + 1

        if nums[start] == target:
            first = start
        elif nums[end] == target:
            first = end
        else:
            return [-1, -1]

        # Last Occurance
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] <= target:
                start = mid
            else:
                end = mid - 1

        if nums[end] == target:
            return [first, end]
        else:
            return [first, start]