算法之二分查找

普通二分

def binary_search(array,value):
    """ 适用于无重复元素 """
    left,right=0,len(array)-1    #注意r=len-1，保证[l,r]闭区间均有值
    while(left<=right):          #闭区间
        mid=left+(right-left>>1)#注意括号
        if array[mid]==value:
            return mid
        elif array[mid]<value:
            left=mid+1
        elif array[mid]>value:
            right=mid-1
    return -1  #无



print(binary_search([1,2,2,2,3],1))
print(binary_search([1,2,2,2,3],2))#找到的位置不是边界
print(binary_search([1,2,2,2,3],3))

print(binary_search([1,2,2,2,3],0))
print(binary_search([1,2,2,2,3],4))

左边界

def lower_boound(array,value):
    """ 左边界 """
    left,right=0,len(array)-1   
    while(left<=right):          
        mid=left+(right-left>>1)#注意位运算的括号
        if array[mid]==value:#左边界的精髓：找到了不返回，继续收缩右边界   
            right=mid-1
        elif array[mid]<value:
            left=mid+1
        elif array[mid]>value:
            right=mid-1
    if(left>=len(array) or array[left]!=value):#判断溢出
        return -1
    return left

print(lower_boound([1,2,2,2,3],1))
print(lower_boound([1,2,2,2,3],2))#找到的位置是左边界
print(lower_boound([1,2,2,2,3],3))

print(lower_boound([1,2,2,2,3],0))
print(lower_boound([1,2,2,2,3],4))