Binary Search

时间复杂度：

T(n) = T(n/2) + O(1) = O(logn)通过O(1)的时间，把规模为n的问题变为n/2

思考:通过O(n)的时间，把规模为n的问题变为n/2?

通用模板：

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