关于二分查找的一些东西

二分查找是比较常见的查找算法，在猜价的节目中就可以用到。 二分查找的时间复杂度为O(logn)。

Python实现：

• 迭代

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

• 递归

def search(nums, target, start, end):
    if start > end:
        return -1
        
    mid = (start + end) // 2
    mid_num = nums[mid] 
    if mid_num > target:
        return search(nums, target, start, mid-1)
    elif mid_num < target:
        return search(nums, target, mid+1, end)
    else:
        return mid