# 二分查找
def binarySearch (arr, l, r, x):

    # 基本判断

    if r >= l:

        mid = (l + r)/2# 中间位置

        if arr[mid] == x:

            return mid

        # 元素小于中间位置的元素，只需要再比较左边的元素

        elif arr[mid] > x:

            return binarySearch(arr, l, mid-1, x) # 这里就需要return,如果不加return,那么当前函数也就是栈底函数就没有返回指（假设这个函数调用两次，虽然第二次调用有返回值，但是没有变量的接收，那么当前函数就没有返回值了）但是这个函数是需要返回指的，矛盾，所以会报错。

        # 元素大于中间位置的元素，只需要再比较右边的元素

        else:

            return binarySearch(arr, mid+1, r, x) # 当然这个也需要return

    else:

        # 不存在

        return -1

# 快速排序

def QuickSort(myList,start,end):

    #判断low是否小于high,如果为false,直接返回

    if start < end:

        i,j = start,end

        #设置基准数

        base = myList[i]

        while i < j:

            #如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现

            while (i < j) and (myList[j] >= base):

                j = j - 1

            #如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等

            myList[i] = myList[j]

            #同样的方式比较前半区

            while (i < j) and (myList[i] <= base):

                i = i + 1

            myList[j] = myList[i]

        #做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base

        myList[i] = base

        #递归前后半区

        QuickSort(myList, start, i - 1)  # 这里就不需要return，因为这个函数最后有return，并且这个返回值是myList,因为当前函数会返回已经被递归函数所修改的myList。所以最后return myList是可以去掉的
        QuickSort(myList, j + 1, end)

    return myList  # 可以去掉