# 分治，递归，合并

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + [pivot] + quicksort(right)

lists=[30,24,5,58,18,36,12,42,39]

print(quicksort(lists))

def func(l, k, left, right):   #l 有序数组，k 目标值
    # 递归退出条件
    if left > right:
        return -1
    middle = (left + right) // 2
    if l[middle] == k:
        return middle
    elif l[middle] > k:
        right = middle - 1
        return func(l, k, left, right)
    else:
        left = middle + 1
        return func(l, k, left, right)