3-1 排序与查找

小节	位置
3.1.1.1	冒泡排序
3.1.1.2	选择排序
3.1.1.3	插入排序
3.1.1.4	希尔排序
3.1.1.5	归并排序
3.1.1.6	堆排序
3.1.1.7	快速排序
3.1.1.8	计数排序
3.1.1.9	基数排序
3.1.1.10	桶排序
3.1.2	二分查找

3.1.1 排序部分

排序算法可以分为内部排序和外部排序，
内部排序是数据记录在内存中进行排序，
外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要额外辅助空间。

3.1.1.1 冒泡排序

它重复地遍历过要排序的数列，每次比较相邻两个元素，如果其大小顺序错误就交换位置。
遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。
(或者也可以让大的元素慢慢“沉”到后面去，这种写法就是右部为有序区域）
冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

# code 写法并不唯一，思路是固定的：通过对比相邻元素，然后交换
# 我这里的写法是每一轮把剩余的一个最大值, 送到右侧去
def Bubble_Sort(x):
    N = len(x)
    for i in range(N-1, 0, -1):
        for j in range(0, i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]
    return x

上述 code 思路：
不断地从左侧对比出最大的值，按次序放在右侧
第一轮:要比较的相邻索引是 (0, 1), (1,2), … ,(N-2, N-1), 遍历完后，最大数落在 N-1 位置
第二轮:要比较的相邻索引是 (0, 1), (1,2), … ,(N-3, N-2), 遍历完后，最大数落在 N-2 位置
…
倒数第二轮，要比较的相邻索引是 (0, 1), (1,2), 遍历完后，最大数落在 2 位置
最后一轮，数据对索引是 (0, 1), 遍历完后，最大数落在 1 位置
故而，如果用 i 代表每一轮的对比的末尾，i 从 N-1 到 1，即 i in range(N-1,0,-1)
用 j 来代表数据待比较区域的索引，j 从 0 到 i-1，即 j in range (0, i)

3.1.1.2 选择排序

每次遍历时，都将未排序区域的第一个值，假设为本次遍历的最小值，
然后开始遍历未排序区域，直到找到未排序区域中最小的值的序号min_Index，
遍历完一次后，比较 min_Index 位置的值与假设的最小值的大小，不及预期，则可以交换位置，同时，未排序区域减少一个位置。
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。
==排序过程中，左侧区域是已排序区域，右侧区域是未排序区域。==

def SelectSort(a):
    for i in range(0,N-1):
        min_index = i
        for j in range(i+1,N):
            min_index = j if (a[j]<a[min_index]) else min_index
        if i != min_index:
            a[i], a[min_index] = a[min_index], a[i]
    return a

code 思路

第一轮:假设 0位置最小，从 1~N-1位置上找到最小的，与0位置比较，看谁更小，更小的放在0位置
第二轮:假设 1位置最小，从 2~N-1位置上找到最小的，与1位置比较，看谁更小，更小的放在1位置
. . .
倒数第二轮，假设 N-3位置最小, 从 N-2~N-1位置上找到最小的，与N-3位置比较，看谁更小，更小的放在N-3位置
最后一轮，假设 N-2位置最小, 从 N-1位置上找到最小的，与N-2位置比较，看谁更小，更小的放在N-2位置
故而，如果用 i 代表每一轮的假设最小位置，则 i 从 0 到 N-2，即 i in range(0,N-1)
用 j 来代表数据每一轮寻找区域的起始值，则 j 从 i+1 到 N-1，即 j in range(i+1,N)

3.1.1.3 插入排序

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。和打扑克时整理排序类似。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

def InsertSort(a):
    for i in range(1,N):
        for j in range(i-1,-1,-1):
            if a[j]>a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a

code 思路

不断地将右侧未排序区域的第一个位置，插入到左侧已排序区域的合适位置上
只有1个元素时不用排序，所以右侧未排序区域的起始位置是1
第一轮:取得 1 位置上的值，与0位置比较，看谁更小，在合适的位置放下
第二轮:取得 2 位置上的值，与0~1位置比较，看谁更小，在合适的位置放下
。。。
倒数第二轮，取得 N-2 位置上的值，与0~N-3位置比较，看谁更小，在合适的位置放下
最后一轮，取得 N-1 位置上的值，与0~N-2位置比较，看谁更小，在合适的位置放下
故而，如果用 i 代表每一轮获得的起始位置，则 i 从 1 到 N-1，即 i in range(1,N)
用 j 来代表数据已排序的位置，则 j 从0 到 i-1，即 j in range(0,i)
但要注意，我们进行对比时，是在已排序区域从右往左对比更方便，因为离i更近。
所以 j 在取的时候，是先看离 i 位置近的 j，即反过来， j in range(i-1, -1, -1)

3.1.1.4 希尔排序

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

def ShellSort(a, d=4):
    N = len(a)
    gap = 1
    while gap < N//d:
        gap = d*gap+1
    # gap 可以理解为分组的数量
    # 这里的 d 其实就是第一次分组后，组内元素的上限
    # 所以这里可以理解为，初始分成gap组，每组内的元素最多d个
    while gap > 0:
        for i in range(gap, N):
            for j in range(i-gap, -1, -gap):
                if a[j] > a[j+gap]:
                    a[j+gap], a[j] = a[j], a[j+gap]
        # 随着循环进行，要将分组数调小
        gap = gap//d
    return a

3.1.1.5 归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
可以使用递归的方法来实现，每一次都将数据分为左右两块，每一次都分别让左右两块各自排好序，然后再将两块 Merge 起来，从而整体有序。

def MergeSort(a,L,R):
    if L>=R:
        return 
    M = L+(R-L)//2
    Mergesort(a, L, M)
    MergeSort(a, M+1, R)
    
    # Merge stage
    p1,p2 = L,M+1
    res =[] # 归并排序申请了辅助空间，所以是 外部排序
    while p1 <=M and p2 <=R:
        # 分离双指针
        if a[p1]<=a[p2]:
            res.append(a[p1])
            p1+=1
        else:
            res.append(a[p2])
            p2+=1
    # 循环结束后，p1、p2中至少有一个已经越界，下面对没有越界的部分连接
    while p1<=M:
        res.append(a[p1])
        p1+=1
    while p2<=R:
        res.append(a[p2])
        p2+=1
    for k in range(len(res)): # len(res) = R-L+1
        a[L+k] = res[k]
    return a

3.1.1.6 堆排序

堆排序需要涉及到一些二叉树的基础知识，但不需要完全了解二叉树，只需要在草稿纸上模拟一下就行。

这里提前介绍一下大/小根堆：
大根堆/小根堆，就是属于完全二叉树；
大根堆：根节点是整棵树的最大值；并且对于每一棵子树而言，其最大值也都在子树根节点
小根堆：根节点是整棵树的最小值；并且对于每一棵子树而言，其最小值也都在子树根节点
下图左侧是大根堆的示意图，右侧是小根堆的示意图：

3.1.1.6.1 数组转成大根堆形式

① HeapInsert 操作

HeapInsert 操作，就是对于新加入数组的元素，我们将其移动到大（小）根堆的合适的位置。
对于新加入的元素，假设其数组索引是 i, 那么在堆中，它的父亲结点的索引就是 int((i-1)/2)。可以自己在画一下完全二叉树验证这个关系。HeapInsert 操作就是将新元素，不断地与其父亲结点的值比较大小，假设是构造大根堆，那新元素若比父亲结点大，它就往上移动（与父亲结点交换），然后再与新的父亲结点比较大小……直到无法再向上移动，即找到它合适的位置了。示意图如下：

这种方式与之前讲的插入排序的思路很像，就是对于下一个数，将它插入到前面结构的合适的位置上，所以这种构造大（小）根堆的方式也被称为 HeapInsert.

def HeapInsert(x, index):
    '''
    # 该函数只是对index位置的值，进行heap insert 操作;时间复杂度：O(logN)
    # 因为最多往上移动的次数 就是 该二叉树的高度：log_2(N)
    # 如果要将一个随机数组构造成 大（小）根堆，则需遍历每一个元素，应用此函数
    '''
    # 这里直接用int取整即可，(//向下取整，会在-0.5时取到-1,当index=0时使用//无法正确取数，所以用int)，
    father = int((index-1)/2)
    while x[index] > x[father]:  #  此处改为小于即可用于生成小根堆
        x[index], x[father] = x[father], x[index]
        # 与父亲结点交换后，index 和 father 都要更新
        index = father
        father = int((index-1)/2)
    return x

那么，如果我们对数组中的元素，从左往右依次进行 HeapInsert 操作，最后就讲这整个数组的数据转变成了大根堆的形式：

def TurnToMaxHeap(arr):
    '''
    问题一：将一个完全二叉树（实际结构是数组）转换成大根堆
    时间复杂度：O(N*logN)
    '''
    for i in range(0, len(arr)):
        # 从 0 开始，将每一个 a[k] 视为新加入的数，构造大根堆
        arr = HeapInsert(arr, i)
    return arr

这里要注意，到这里为止，只是将数组处理为大(小)根堆，并未完成排序。

② Heapify 操作

上面的 HeapInsert 操作是对新来的数字“往上浮”，这里讲的是对原有的数字“往下沉”。

def Heapify(a, index, heapsize):
    '''
    heapify过程：将一个原本是大根堆的完全二叉树，根结点的值发生变化，要重新变成大根堆的过程.
    方法：index位置的元素和它的左右孩子比较，如果小于它的左右孩子那么就往下沉；否则不动
    时间复杂度Olog(N)
    heapsize小于等于数组最后一个索引(也就是表示0~heapsize区间是个大根堆)；
    '''
    left = 2 * index +1
    while left <= heapsize:
        right = left + 1
        # 先比较左右孩子中更大的结点
        large = right if (right <= heapsize and a[right]>a[left]) else left
        # 再比较当前结点与最大孩子的值
        large = large if (a[large] > a[index]) else index
        # 如果最大的是当前结点，说明不需要下沉了，停止循环
        if large == index:
            break
        # 否则就交换位置，并更新索引，准备下一轮循环
        a[index], a[large] = a[large], a[index]
        index = large
        left = 2*index + 1
    return a

因为我们上面code的前提条件是，假设“一个原本是大根堆的完全二叉树，根结点的值发生变化，重新调整根结点的位置，使其恢复为一个大根堆”；所以对于一个本来不是大根堆的完全二叉树，想要利用Heapify的思路转换成大根堆，就从下往上进行变换。
即从倒数第二层开始，让每一个子树都称为大根堆，不断往上扩展。子树变成大根堆后，它的父节点就可以视为外层大根堆被改变了值的那个根结点，又将该父结点下沉到合适位置，又再往上扩张一层。具体实现code 如下：

def BuildMaxHeap(a):
    '''时间复杂度O(N)'''
    import math
    N = len(a)
    for i in range(math.floor(N/2), -1, -1):
        a = Heapify(a, i, N-1)
    return a

为何用这种方法构造大根堆的时间复杂度是O(N)? 解释如下：

对于一棵满的完全二叉树，二叉树一共有 N 个结点。则：
倒数第1层有 $\frac{N}{2}$ 个结点，每个结点遍历1次，最多往下沉 0 次，总共就是 $\frac{N}{2}$ 次操作；

倒数第2层有 $\frac{N}{4}$ 个结点，每个结点遍历1次，每个结点最多往下沉 1 次，总共就是 $\frac{2N}{4}$ 次操作；

倒数第3层有 $\frac{N}{8}$ 个结点，每个结点遍历1次，每个结点最多往下沉 2 次，总共就是 $\frac{3N}{8}$ 次操作；
……
所以时间复杂度为 $T(N) = \frac{N}{2} + \frac{2N}{4} + \frac{3N}{8} + \cdots $
故而 $T(N) = 2T(N) -T(N) = N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + \cdots - \sigma $ 这是一个等比数列，结果是 $2N$，所以时间复杂度就是 $O(N)$。

3.1.1.6.2 堆排序部分

假设是按照从小到大排序，那么每一次构造一个大根堆后，未排序区域的最大值就到了根结点，那么只要将该数与未排序区域末尾数交换，则该区域的最大数就到了该区域的末尾。同时未排序区域缩小一格，然后恢复未排序区域的大根堆结构，重复操作。

def HeapSort(a):
    N = len(a)
    # 先构建大根堆
    a = buildMaxHeap(a)
    for k in range(N-1, -1, -1):
        # 每一次都将顶点和最后最后一个数进行交换，则最大数就被移动到数组末尾
        a[0], a[k] = a[k], a[0]
        # 相当于 a[0] 的位置发生了变化，正好用heapify重新调整为大根堆
        # 注意刚刚的最大值已经是有序区域中了，所以heapsize也要每次缩小一次
        a = Heapify(a,0,k-1)
    return a
    '''
    可以看到，不管最开始采用哪种方法构造大根堆，O(N)或者O(N*logN)都无所谓
    后面不断交换位置的操作才是影响时间复杂度的大头，这部分是 O(N*logN)
    所以堆排序的总体时间复杂度是 O(N*logN)
    '''

3.1.1.7 快速排序

快速排序采用的思想也是分治法，先将数组大致分为有序的几块区域，再对各个区域内分为几个有序的区域，直到区域已经不可再细分，这样整个数组也就有序了。下面只给出快速排序的code，至于其推导过程，见下一章【快速排序深入讨论】。

快速排序虽然表面上只用了几个额外的变量，但是其空间复杂度是O(logN)!
这是因为快速排序使用递归操作，递归操作会调用系统栈，这个系统栈的深度是O(logN)。

def QuickSort(a, L, R):
    if L >= R:
        return a
    # partition stage:
    # 随机抽取一个基础值
    key = random.randint(L, R)
    a[key], a[R] = a[R], a[key]
    # 将基础值放在最右方便下面写code
    key = R
    p1, p2 = L-1, R
    # 这一段partition已经是经过荷兰国旗问题优化后的partition了，原始的快速排序不是这么写
    i = p1+1
    while i < p2:
        if a[i] < a[key]:
            # 如果 i 位置的值更小，i与小于区域的下一位的数交换，小于区域扩张1位
            a[i], a[p1+1] = a[p1+1], a[i]
            p1 += 1
            i += 1
        elif a[i] == a[key]:
            # 如果相等，i直接往后过，两个区域都不变化
            i += 1
        else:
            # 如果i位置的值更大，i与大于区域的左侧数交换，大于区域扩张(p2减少1)
            a[i], a[p2-1] = a[p2-1], a[i]
            p2 -= 1
            # 同时i不变，因为i位置的数刚从大于区域的左侧被交换过去，还没判断呢
    # 循环结束后 i==p2，i位置的值一定大于等于key位置
    # 将基础值与i位置进行交换
    a[i], a[key] = a[key], a[i]
    # recursion stage
    QuickSort(a, L, p1)
    QuickSort(a, p2+1, R)
    return a

3.1.1.8 计数排序

要求元素一定是整数！整数！且元素值的范围最好不要太大，一般来说几万以内应该都还算比较快。
计数排序不是比较排序，排序的速度快于任何比较排序算法，只不过有上一行提到的先决条件。
基本思路如下：
① 找出待排序的数组中最大和最小的元素，因为计数的数组Count的长度取决于待排序数组中数据的范围，
② 创建计数数组Count，长度等于待排序数组的最大值与最小值的差加上1,元素默认值为0.
③ 遍历原数组中的元素，以原数组中的元素值作为Count数组的索引，以原数组中的元素出现次数作为Count数组的元素值。
比如原始数组中有10个66，则Count[66]=10
④ 按照count索引从小到大（也就是原始数组元素值从小到大）进行遍历，排布好新的数组

def CountSort_1(a):
    '''最基础的情况，元素都为非负整数'''
    # 1.获得最大值
    # 如果不想用自带的max函数，那其实也可以遍历一遍数组，时间复杂度也是O(N)
    # 因为计数排序本来就是O(N+K)，时间复杂度是忽略系数的，O(N) + O(N) 还是 O(N)
    max_v = max(a)
    # 2.创建辅助数组
    count_list = [0]*(max_v+1)
    # 3.统计原数组的元素出现的次数
    for k in range(len(a)):
        count_list[a[k]] += 1
    # 4.对原始数组的元素按顺序排布
    i = 0
    for k in range(len(count_list)):
        while count_list[k] > 0:
            a[i] = k
            count_list[k] -= 1
            i += 1
        # 这一段 while 循环体虽然可以改写成如下形式：
        # if count_list[k] > 0:
        #     a[i:i+count_list[k]] = [k]*count_list[k]
        #     i += count_list[k]
        # 但是 python在实际操作中会 在等号右边创建一个临时的数组，然后赋值给左边
        # 这就相当于使用了 额外空间了，所以不建议这么写
    return a

def CountSort_2(a):
    '''若可能有负数出现，只需要引入一个bias即可'''
    # 1.获得最大值，最小值
    min_v, max_v = min(a), max(a)
    # bias = 0-min_v if min_v < 0 else 0
    bias = - min(0, min_v)
    # 2.创建辅助数组
    count_list = [0]*(max_v+1+bias)
    # 3.统计原数组的元素出现的次数
    for k in range(len(a)):
        count_list[a[k]+bias] += 1
    # 4.对原始数组的元素按顺序排布
    i = 0
    for k in range(len(count_list)):
        while count_list[k] > 0:
            a[i] = k - bias
            count_list[k] -= 1
            i += 1
    return a 
    # 可见这个写法不管有没有负数, 其实都能跑通

从代码中可以看出，计数排序的时间复杂度是 O(n+k), 空间复杂度是O(k)
其中n是数组规模， k是数组值域范围 max_v - min_v + 1

3.1.1.9 基数排序

所谓的基数，就是指的按照数字的哪一位来排序。
比如按照个位来排序，基数就是 10^0;
按照十位数进行排序，基数就是 10^1;
按照百位数进行排序：基数就是 10^2;
基数排序也不用进行比较，因为每一位数字都是 0-9组成的，天然有序，所以只要按照每一位的数字，将数字分到对应的分组去，那么对于当前位数来说，各个组之间就按照0-9排序了。
对于每一位都来一次，就能够实现整体有序。

基数排序能够实现有序的关键点在于，当按照分组分号之后，从分组中取出来排布时，各个分组的元素要做到先入先出。因为同一个分组内的元素，当前考察的基数那一位，肯定是相同的，但是其进入分组的顺序，是由上一轮的考察基数位的大小顺序决定的。

举个例子：比如 58和51 被分到了一个分组，可以肯定，当前考察的是十位，因为它们的十位都是数字5，这才有可能被分到一个分组。那么上一轮考察的就是个位，个位分别是 1 和 8，那么可以肯定，1这个分组的数字是排在8这个分组的数字之前的。

所以在考察十位上的数字进行分组时，一定是 51先遍历到，被分到5号组，然后才是58被遍历到，也分到5号组。所以组内的顺序是: [ 51, 58 ]。那么从分组内取出进行还原时，就要保证先取出 51，再取出 58。所以各个分组，其实可以从逻辑上视为一个队列。当然不必真的使用队列，只要使用 list 时注意先入先出的顺序就好。

基数排序通常也是只能处理非负整数，且要求数目不要过大。

def RadixSort(a):
    '''最基础的情况，元素都为非负整数'''
    max_v = max(a)
    # d 这里在统计最高的位数
    # d=0
    # while max_value >0:
    #     d+=1
    #     max_value//=10
    d = len(str(max_v))

    for i in range(d):
        radix = 10 ** i # radix 代表本次循环基于哪一个位
        # 每一轮都是重新初始化 Groups
        Groups = [[] for _ in range(10)] # 初始化从0到9，共10个分组

        for num in a:
            digit = num // radix % 10
            # 按照当前位的数字，将原始数据分别装入不同的group中
            Groups[digit].append(num)

        # 该 print 函数能打印各个阶段 数字装入分组后的状况，
        # 可以取消注释后打印中间结果，帮助理解
        # print(i, Groups)        
        j = 0
        for group in Groups:
            for num in group:
                a[j] = num 
                j += 1
    return a

稍加改动也能处理出现负整数的情况
对于负数部分，我们需要在设置一个长度为 10 的分组，用来装 -9 — 0 。
这里需要注意的点，

① 10 和 -10 与 10% 进行求模运算后，结果都是 0；但是这两个数明显不能都放入 0 号组，
10 是可以放入 0 号分组的，但是 -10 却是一个负数，它的实际位置应该比0还小。
```
为了方便讨论，我们这里称呼 -10 % 10 为 -0；在负数部分的分组中，排在最大的位置。
 即负数的10个分组对应的数字为：[-9], [-8], ..., [-1], [-0]
```
② 在求每一位上的数字时，我们之前使用的是整除号：// 。但是整除号是向下进位，对负数使用整除号时，会往远离 0 的方向进位。比如 -18 // 10 = -2; 但是我们希望是得到 - 1，这样能照搬非负整数部分的处理，所以就是希望向 0 靠拢。可以使用 int函数。int(-18 / 10 ) = -1.

def RadixSort_2(a):
    '''要处理的数据中可能出现 负整数'''
    max_v, min_v = max(a), min(a)
    # d 这里在统计最高的位数

    # 如果存在负数，str之后会有'-'，即比数字本身多了1位，所以需要判断
    L_1 = len(str(max_v)) if max_v > 0 else len(str(max_v))-1
    L_2 = len(str(min_v)) if min_v > 0 else len(str(min_v))-1
    d = max(L_1, L_2)
    
    for i in range(d):
        radix = 10 ** i # radix 代表本次循环基于哪一个位
        Groups = [[] for _ in range(10)] # 初始化从 0 到9，共10个分组
        Groups_neg = [[] for _ in range(10)] # 初始化从-9 到-0，共10个分组

        for num in a:
            # digit = num // radix % 10
            digit = int(num / radix) % 10
            # 注意: -10 和 10 与 10 求模运算后都得 0
            # 但是二者的大小明显不一样
            # 为了便于理解，我们可以假设 10 % 10 = +0； -10 % 10 = -0
            # 按照当前位的数字的正负属性，将原始数据分别装入不同的group中
            if num >= 0:
                Groups[digit].append(num)
            else:
                # 这里需要注意 -9 % 10 = 1;...; -1 % 10 = 9; -10 % 10 = -0;
                Groups_neg[digit-1].append(num)
        
        # 该 print 函数能打印各个阶段 数字装入分组后的状况，
        # 可以取消注释后打印中间结果，帮助理解
        # print(i, Groups_neg, '---', Groups)
        j = 0
        # 先取出负数部分
        for group in Groups_neg:
            for num in group:
                a[j] = num 
                j+=1

        # 再取出正数部分
        for group in Groups:
            for num in group:
                a[j] = num 
                j += 1
    return a

从代码中可以看出，基数排序的时间复杂度是 O(n*k), 空间复杂度是O(n)
其中n是数组规模， k是数组中位数最长的一个数的宽度

3.1.1.10 桶排序

将数据分到若干个桶（分组）中，每个桶的元素再进行单独排序。
通常是按照数值大小进行分组，比如若一个数组最大数为 200，最小数为1，就可以以 20的区间进行分组，分10个桶。但是有一些题目可能也会根据另外一些属性进行分组，总之要看具体情况。
对每个桶内的数据进行排序操作，也是看数据的具体情况，可以使用不同的排序方法。
最后将各个桶内的元素组合到一起，完成最终排序。

3.1.2 二分查找

二分查找的时间复杂度是O(logN),参考链接

def BinarySearch (arr, L, R, x): 
  
    # 基本判断
    if R >= L: 
  
        mid = L + int((R - L)/2)
  
        # 元素整好的中间位置
        if arr[mid] == x: 
            return mid 
          
        # 元素小于中间位置的元素，只需要再比较左边的元素
        elif x < arr[mid]: 
            return BinarySearch (arr, L, mid-1, x) 
  
        # 元素大于中间位置的元素，只需要再比较右边的元素
        else: 
            return BinarySearch (arr, mid+1, R, x) 
  
    else: 
        # 不存在
        return -1