python查找算法问题总结

1、单个元素查找（有序）

查找第一个值等于给定值的元素下标

def binary_search(sorted_list:list,aim:int):
    low=0
    high=len(sorted_list)-1
    while low<=high:
        mid=low+(high-low)//2 
        # mid=(low+high)//2
        if sorted_list[mid]>aim:
            high=mid-1
        elif sorted_list[mid]<aim:
            low=mid+1
        else:
            if mid==0 or sorted_list[mid-1]!=aim:
                return mid #变形可以查找最后一个小于给定值的元素下标mid-1
            high=mid-1
    return -1

查找最后一个值等于给定值的元素下标

def binary_search(sorted_list:list,aim:int):
    low=0
    hight=len(sorted_list)-1
    while low<=high:
        mid=low+(high-low)//2
        #mid =(high+low)//2
        if sorted_list[mid]>aim:
            high=mid-1
        elif sorted_list[mid]<aim:
            low=mid+1
        else:
            if mid==len(sorted_list)-1 or sorted_list[mid+1]!=aim:
                return mid # 变形可以查找第一个大于给定值的的元素下标mid+1
            else:
                low=mid+1
        return -1

查找第一个大于等于给定值的元素下标

def binary_search(sorted_list:list,aim:int):
    low=0
    high=len(sorted_list)-1
    while low<=high:
        mid=low+(high-low)//2
        # mid=(low+high)//2
        if sorted_list[mid]<aim:
            low=mid+1
        else:
            if mid==0 or sorted_list[mid-1]<aim: 
                return mid
            else:# 中间位置的值不是第一个大于等于给定值的值，向下找
                high=mid-1
    return -1   

查找最后一个小于等于给定值的元素下标

def binary_search(sorted_list:list,aim:int):
    low=0
    high=len(sorted_list)-1
    while low<=high:
        mid=low+(high-low)//2
        #mid=(high+low)//2
        if sorted_list[mid]>aim:
            high=mid-1
        else:
            if mid==len(sorted_list)-1 or sorted_list[mid+1]>aim:
                return mid
            else:# 中间位置的值不是最后一个小于等于给定值的值，向上找
                low= mid+1
    return -1

2、集合元素查找（有序）

查找所有值等于给定值的元素

sorted_list[查找第一个值等于给定值的元素下标:查找最后一个值等于给定值的元素下标+1]

查找所有值大于给定值的元素

sorted_list[查找最后一个值等于给定值的元素下标+1:]

查找所有值小于给定值的元素

sorted_list[:查找第一个值等于给定值的元素下标+1]

查找所有值大于等于给定值的元素

sorted_list[查找第一个大于等于给定值的元素下标:]
或
sorted_list[查找第一个值等于给定值的元素下标:]

查找所有小于等于给定值的元素

sorted_list[:查找最后一个小于等于给定值的元素下标+1]
或
sorted_list[:查找最后一个值等于给定值的元素下标+1]