当前位置 : 主页 > 编程语言 > python >

【算法实践】一天路走到黑--手把手带你实现坚持不懈的线性查找

来源:互联网 收集:自由互联 发布时间:2023-02-04
前言 什么是线性查找? 线性查找又称为顺序查找,它是最基础的一种查找算法.线性查找的做法非常简单,简单到见名知意:在一列给定的值中进行搜索,从一端开始逐一检查每个元素,直到

前言

什么是线性查找?

线性查找又称为顺序查找,它是最基础的一种查找算法.线性查找的做法非常简单,简单到见名知意:在一列给定的值中进行搜索,从一端开始逐一检查每个元素,直到找到所需元素的过程。线性查找是从第一个记录开始,与记录的关键字逐个比较,直到和给定的关键字相等,则就是查找成功,如果比较的结果与文件中所有记录的关键字都不相等,则查找失败,如果查找池是某种类型的一个表,比如一个数组,简单的查找方法是从表头开始,一次将每一个值与目标元素进行比较,最后,或者查找到目标,或者达到表尾,而目标不存在于组中,这个方法称为线性查找。

举个现实中的例子:比如刚开学,小北的爸妈来学校找他,小北爸妈不知道小北住那个宿舍,这时他们找宿管阿姨,但是由于刚开学没来得及登记入住信息,宿管也不知道小北具体住哪个宿舍,只知道住哪个楼层,这样宿管阿姨就只能带着小北的爸妈第一间到最后一间逐个宿舍问,直到找到小北为止,这就是线性查找

因为线性查找需要从头开始不断地按顺序检查数据,因此在数据量大且目标数据靠后的情况,或者数据不存在时,比较次数会更多,且更耗时.线性查找的平均查找长度和表长度n成线性关系,若数据量为n,那么线性查找的平均次数为: n/2;时间复杂度为O(n),当n较大时线性查找的效率较低,不过的它优点在于简单且容易实现

线性查找的具体流程

  • 输入查找的元素
  • 判断待查找的元素是否存在于数组中
  • 如果存在于数组中,则返回该元素的索引,如果不存在,则返回-1
  • 如果返回索引,则输出该元素的索引位置,否则,则输出"没有找到对应元素"
  • 具体流程如下图:

    【算法实践】一天路走到黑--手把手带你实现坚持不懈的线性查找_线性查找

    操作步骤:

    比如有[1,2,3,4,5,6,7,8,9,10],10个元素的数组,我要从中找到9

    注:数组可以是无序的,这里只是为了演示方便!

    【算法实践】一天路走到黑--手把手带你实现坚持不懈的线性查找_数组_02

    代码实现

    线性查找的代码极其简单:

    def LinearSearch(arr, n, x): for i in range(0, n): if (arr[i] == x): return i return -1

    验证算法:

    data = [15, 18, 2, 14, 26, 13, 19,50, 23, 25, 88, 66, 45, 78, 10, 23, 45]x = int(input("请输入你需要查找的元素:"))n = len(data)result = LinearSearch(data, n, x)if (result == -1): print("没有找到对应元素")else: print("元素在数组中的索引为:", result)

    执行结果如下:

    【算法实践】一天路走到黑--手把手带你实现坚持不懈的线性查找_线性查找_03

    【算法实践】一天路走到黑--手把手带你实现坚持不懈的线性查找_数据_04

    网友评论