#二分法
def erfenfa(lis,target):
    start,end=0,len(lis)-1
    while True:
        if end-start<=1:
            if target==lis[start]:
                return start
            elif target==lis[end]:
                return end
            else:
                return -1
        mid = (start+end)//2
        if lis[mid] <=target:
            start = mid
        else:
            end = mid


lis=[1,2,3,5,7,8]

print(erfenfa(lis,9))



# 快速排序法
def quick(arr):
    if not arr:
        return []
    mid = arr[0]
    left = quick([i for i in arr[1:] if i<mid])
    right = quick([i for i in arr[1:] if i>=mid])
    return left + [mid] + right


lis = [1,3,5,7,2,43,4,8,5,3,1]
print(quick(lis))