数据结构-查找-顺序查找法

谁借莪１个温暖的怀抱￠ 2023-10-04 16:28 85阅读 0赞

在数据处理的过程中，是否能在时间内查找到所需要的数据是一个相当值得重视的问题。所谓查找(search)，指的是在数据文件中找出满足某些条件的记录。用以查找的条件称作为“键值(Key)”，就如同排序所用的键值一样。

#### 常见的查找方法 ####

根据数据量的大小，我们可以将查找分为内部查找和外部查找

*  内部查找：数据量较小的文件可以一次性全部加载到内存中进行查找
 *  外部查找：数据量大的文件无法一次性加载到内存中处理，而需要使用辅助存储器来分次处理

如果从另一个角度来看，查找的技巧又可以分为“静态查找”和“动态查找”两种

*  静态查找：指的是在查找过程中，查找的表格或者文件的内容不会被更改，例如符号表的查找就是一种静态查找
 *  动态查找：指的是在查找的过程中，查找的表格或者文件内容可能被改动，例如树状结构中的B-Tree查找就属于一种动态查找

查找技巧中比较常见的有顺序法、二分查找法、斐波拉契法、插值法、哈希法等等

#### 顺序查找法 ####

顺序查找法又称作是线性查找法，是一种最简单的查找法。他的方法就是将数据一项一项的按照顺序逐个查找，所以无论数据的顺序是什么样，都得从头到尾遍历一次。次方法的有点就是文件在查找前不需要进行任何处理与排序，缺点就是查找速度较慢。如果数据没有重复，找到数据就可以中止查找，最差情况下是未找到数据，而需要进行n次比较，在最好情况下则是一次就能找到数据，只需要1次比较。

1.  **顺序查找法的分析**  
    时间复杂度：如果数据没有重复，找到数据就可以中止查找，在最差情况下是未找到数据，而需进行n次比较，时间复杂度为O(n)
2.  在平均情况下，假设数据出现的概率想到，则需要进行(n+1)/2次比较
3.  当数据量很大时，不适合使用顺序查找法。但如果预估所查找的数据在文件的前段，选择这种查找法则可以减少查找的时间

**设计一个程序，随机生成1-150的80个整数，实现顺序查找法**

"""
    随机生成1-150的80个数字，完成顺序查找
    """
    import random
    
    data = [0] * 80
    for i in range(80):
        data[i] = random.randint(1,150)
    
    val = 0
    while val != -1:
        find = 0
        val = int(input("请输入查找的数字(1-150),输入-1离开："))
        for i in range(80):
            if data[i] == val:
                print("在第%3d个位置找到了[%3d]"%(i+1,val))
                find += 1
        if find == 0 and val != -1:
            print("#########没有找到[{}]###########".format(val))
    print("数据内容是：")
    for i in range(10):
        for j in range(8):
            print("%2d[%3d]\t"%(i*8+j+1,data[i*8+j]),end='')
        print()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210702131913297.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjQyOTI5MA==,size_16,color_FFFFFF,t_70