Binary Tree

题目描述

虽然概念很简单，但是binary search在code的时候还是很容易写错，要自己多写几遍，注意 corner case。

题目列表

sorted array

sqrt, power

模板

binary search可以有多种写法，如果每次都写的不一样，就会造成对于结束条件，指针变化的混乱，所以我们要找到一种固定的模板，通过修改模板来解决题目。这里我选择了九章算法提供的模板。 四点要素:

1. start + 1 < end 这样就不用考虑两个指针的前后，最后结束时一定是相邻的
2. start + (end - start) / 2 虽然对python来说不重要，但是对于Java等可以防止溢出
3. A[mid] ==, <, > 这个会根据题目的不同来调整
4. A[start] A[end] ? target

class Solution:
    # @param nums: The integer array
    # @param target: Target number to find
    # @return the first position of target in nums, position start from 0 
    def binarySearch(self, nums, target):
        if len(nums) == 0:
            return -1

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

        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1

最终状态都是要将start和end位置的值与target来比较，根据题意得到想要的结果

Reference