第一类

• search insert position
• search for a range
• isBadVersion
• Closest Binary Search Tree Value
• Find Peak Element
• Median of Two Sorted Arrays

这两道题目是考察基本用法，但是因为题目没有告诉你是否有重复的值，所以并不能mid = target就停下来，而是要继续查找

Search insert position

基本二分法的思想

• mid >= target时end = mid继续搜
• mid < target是start = mid继续搜
• 最终用start和end来比较，如果有>=的，就插入在这里，如果都小于，说明应该插入在list的结尾

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:
            return -1

        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] >= target:
                #can not stop when equal, should continue search
                end = mid
            else:
                #start = mid + 1 is also fine
                start = mid

        #start, end, compare them with target, to find the right position
        if nums[start] >= target:
            return start
        if nums[end] >= target:
            return end
        #reach the end of array
        return len(nums)

Search for a range

找左右边界的关键是当mid == target时移动start还是移动end

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = -1
        right = -1
        if len(nums) == 0:
            return [left, right]

        start, end = 0, len(nums) - 1

        #search left 
        #找左边界是一个不断将搜索区间的end不断左移的过程，所以当mid >= target时，就将end移到mid的位置
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] >= target:
                end = mid
            else:
                start = mid

        if nums[start] == target:
            left = start
        elif nums[end] == target:
            left = end
        else:
            #not found
            return [-1,-1]

        start, end = 0, len(nums) - 1
        #search right
        #找右边界是一个不断将搜索区间start右移的过程，当mid <= target时，将start移到mid
        while start + 1 < end:
            mid = start + (end-start)/2
            if nums[mid] <= target:
                start = mid
            else:
                end = mid

        if nums[end] == target:
            right = end
        elif nums[start] == target:
            right = start
        else:
            #not found
            return [-1, -1]

        return [left, right]

isBadVersion

就是binary search

Closest Binary Search Tree Value

一开始看没找到感觉，还以为left <= target, right >= target是我们要找的值。用一个例子来走一遍找找感觉。

对于每一个root,先求得当前的diff, 如果target比root大，说明root左边的值的diff肯定比当前的大，可以舍去左边一半。 右边同理。 就相当于一个binary search.

• refrence

class Solution(object):
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if not root:
            return None

        result, diff = self.helper(root, target)
        return result

    def helper(self, root, target):
        result = root.val
        diff = abs(root.val - target)

        if target >= root.val:
            if root.right:
                rightResult, rightDiff = self.helper(root.right, target)
                if diff > rightDiff:
                    result = rightResult
                    diff = rightDiff
        else:
            if root.left:
                leftResult, leftDiff = self.helper(root.left, target)
                if diff > leftDiff:
                    result = leftResult
                    diff = leftDiff
        return result, diff

recursion解法可以转换为while loop，更高效

class Solution(object):
    def closestValue(self, root, target):
        """
        :type root: TreeNode
        :type target: float
        :rtype: int
        """
        if not root:
            return None

        result = None
        minDiff = sys.maxint
        while root:
            diff = abs(root.val - target)
            if diff < minDiff:
                result = root.val
                minDiff = diff

            if diff == 0:
                break

            if target >= root.val:
                root = root.right
            else:
                root = root.left


        return result

Find Peak Element

link

其实也就是二分法，如果Mid不是peak的话，那么大于它的那一边一定有peak,以为如果一直递增的话，到了边界也一定会有一个peak. 所以每次可以舍去二分之一。

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length == 0:
            return 

        if length == 1:
            return 0

        start, end = 0, length - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
                return mid
            elif nums[mid] < nums[mid - 1]:
                end = mid
            else:
                start = mid

        if nums[start] > nums[end]:
            return start
        else:
            return end

Median of Two Sorted Arrays

方法1 count， brute force

两个指针，一边比较一遍计数

方法2，每次比较两个array的中间值

利用find kth Number的思想

Reference

• 九章