编程题 - 二分搜索查找有序数组的插入位置

 

A = [0,1,2,3,4,5,6,6,6,7,8,9,10]

def bin_find(A,num):
    if(len(A)==0):
        return -1
    n = len(A)
    if(A[0]>=num):
        return 0
    if(A[n-1]<=num):
        return n
    begin = 0
    end = n  
    while(begin<end):
        print(A[begin:end])
        print(begin,end)
        mid = (begin+end)//2
        if(A[mid]<num and A[mid+1]>=num):
            return mid
        elif(A[mid]>=num and A[mid+1]>=num):
            end = mid
        elif(A[mid]<num and A[mid+1]<num):
            begin = mid
    return -1

print(bin_find(A,6))

这里使用mid+1作为前一个位置判断比较合适，因为begin<end,那么mid = (begin+end)//2在区间比较小的时候会等于begin，那时候mid+1的值为end，合法。