python之二分法排序附送第三种最快排序法

发表于 更新于 分类于 ， Changyan： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

每次能够排除掉一半的数据. 查找的效率非常高. 但是局限性比较大. 必须是有序序列才可以使用二分查找

要求: 查找的序列必须是有序序列.

例1、正常二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# num为用户要查找的数字
num =8
# lis为用户查找的范围有序list
lis = [1, 3, 4, 6, 8, 9]
# 初始左边界为0
left = 0
# 初始右边界为最后列表最后一个元素的索引
right = len(lis)-1
# 左边界小于或者等于右边界意味着查找中
while left <= right:
    # 取列表中间元素的索引(索引只能为整数)
    middle = (left + right) // 2
    # 用户查找的值小于中间值，意味着用户要查找的值在左半边，右边边界就可以缩小到中间元素索引的前一位
    if num < lis[middle]:
        right = middle - 1
    # 用户查找的值大于中间值，意味着用户要查找的值在右半边，左边边界就可以缩小到中间元素索引的后一位
    if num > lis[middle]:
        left = middle + 1
    # 用户查找的值等于中间值，意味着找到了该数字
    if num == lis[middle]:
        print('找到了', middle)
        break
else:
    print('未找到')

例2、递归二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 查找数字
# num 要查找的数字
# lis 查找的范围
# left 查找的左边界
# right 查找的右边界
def func(num, lis, left, right):
    # 左边界小于或者等于右边界意味着查找中
    if left <= right:
        # 取列表中间元素的索引(索引只能为整数)
        middle = (left + right) // 2
        # 用户查找的值小于中间值，意味着用户要查找的值在左半边，右边边界就可以缩小到中间元素索引的前一位
        if num < lis[middle]:
            right = middle - 1
            return func(num, lis, left, right) #此处return必须添加，否则数据返回不到上一层，最终结果就会拿不到
        # 用户查找的值大于中间值，意味着用户要查找的值在右半边，左边边界就可以缩小到中间元素索引的后一位
        if num > lis[middle]:
            left = middle + 1
            return func(num, lis, left, right) #此处return必须添加，否则数据返回不到上一层，最终结果就会拿不到
        # 用户查找的值等于中间值，意味着找到了该数字
        if num == lis[middle]:
            return middle
    else:
        return -1
lis = [1, 3, 4, 6, 8, 9]
ret = func(9, lis, 0, len(lis)-1)
print(ret)

例3、切片二分查找法(优点：代码少；缺点：获取不到查找结果的索引)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 查找数字
# n 要查找的数字
# lis 查找的范围
def func(lis, n):
    # # 初始左边界为0
    left = 0
    # # 初始右边界为最后列表最后一个元素的索引
    right = len(lis) - 1
    if left <= right:
        # 取列表中间元素的索引(索引只能为整数)
        middle = (left + right) // 2
        # 用户查找的值小于中间值，意味着用户要查找的值在左半边，直接使用切片将左半边列表作为一个新的列表传入下次递归
        if num < lis[middle]:
            return func(lis[:middle-1], n)
        # 用户查找的值大于中间值，意味着用户要查找的值在右半边，直接使用切片将右半边列表作为一个新的列表传入下次递归
        elif num > lis[middle]:
            return func(lis[middle+1:], n)
        # 用户查找的值等于中间值，意味着找到了该数字
        else :
            return 1
    else:
        return -1
num = 7
lis = [1, 3, 4, 6, 8, 9]

ret = func(lis, num)
print(ret)

最后附送一个面试查找算法，时间空间都最优的写法(直接取值)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 查找数字
# n 要查找的数字
# lis 查找的范围
def func(lis, n):
    # 此处我们定义一个索引列表，长度为lis最后一个元素值大小，并将每项都赋值为0
    indexList = [0 for item in range(lis[-1]+1)]
    # 循环将要查找到范围写入到索引列表index，范围元素对应的索引列表元素值为1
    for i in lis:
        indexList[i] = 1
    # 如果要查找的数字在范围内，并且其作为索引对应的值为1，代表勋在
    if n < len(indexList) and indexList[n] == 1:
        return 1
    else:
        return -1
lis = [1, 3, 4, 6, 8, 9]
ret = func(lis, 15)
print(ret)