Python实现二分法检索(binary search)

二分法检索(binary search)又称折半检索,二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组(array)中。

首先将给定值key与字典中间位置上元素的关键码(key)比较,如果相等,则检索成功;

否则,若key小,则在字典前半部分中继续进行二分法检索;

若key大,则在字典后半部分中继续进行二分法检索。

这样,经过一次比较就缩小一半的检索区间,如此进行下去,直到检索成功或检索失败。

偶数个取中间2个其中任何一个作为中间元素;

二分法检索是一种效率较高的检索方法,要求字典在顺序表中按关键码排序。

items = [1,2,3,4,5,6,7,8,9,10,11,
        12,14,14,15,16,17,18,19,20]

def binSearch(lst, x):
    i = 0
    j = len(lst)
    while i != j:
        m = (i + j) // 2
        if x == lst[m]:
            return m
        if x < lst[m]:
            j = m
        else:
            i = m + 1
    return None

print(binSearch(items, 1))  # 0

print(binSearch(items, 7))  # 6

print(binSearch(items, 19)) # 18

原创内容,如需转载,请注明出处;

本文地址: https://www.perfcode.com/p/1227.html

分类: 计算机技术
推荐阅读:
requests实现更复杂的POST 通常,你想使用requests模拟HTML中的表单内容。你只需要将一个字典传递给 data 参数;requests会将你的数据字典自动编码为表单的形式。
Python repr()函数 在Python中,repr()函数用于获取一个对象的字符串表示形式,通常被用于调试和日志记录。这个字符串是可以用来重新创建该对象的一个有效的表达式。
Python eval()函数 在Python中,eval()是一个内置函数,用于将一个字符串作为Python表达式执行,并返回表达式的结果。
没有main()函数的C语言程序 有两种方法可以不添加main()函数来运行C语言程序,第一种用#define预处理指令,第二种是使用-nostartfiles编译选项;
编程中foo、bar、baz的含义 在编程中,foo、bar和baz通常被用作示例变量名。它们是一种惯用的命名习惯,通常被用于示例代码或临时代码片段中,表示没有特定含义的变量名或函数名。
PySide6 使用QIcon为按钮添加图标 在PySide6中为按钮添加图标,可以使用QIcon类来加载图标文件,并使用QPushButton类的setIcon()方法将图标设置给按钮;