顺序查找

来自计算思维百科
跳转至: 导航搜索
顺序查找1.png

我们想在给定的数据中找到自己想要的数据,就是查找。顺序查找是查找方法中最简单的一种方法。

基本概念

我们把要查找的元素称为查找键,然后从给定数据序列中一个一个地顺序比较,看它是否与查找键相同,如果相同就查找成功,如果找到最后一个元素还没有找到就是查找失败。

可以应用一个小技巧:将查找键添加到列表末尾,则查找一定成功,就不必每次检查时都要看是否到了数据序列的末尾。

应用范围

顺序查找是非常常用的一种查找方法,凡是需要查找的地方都可以用到。

使用方法及步骤

  1. 设置哨兵,即将查找键key放置集合A的末尾;
  2. 按顺序将集合中的元素与查找键一一比较,遇到第一个与查找键相等的元素即停止比较;
  3. 若该元素的位置不大于原有集合数则查找成功,若大于则查找失败。

应用案例

应用1-在数组中查找某个数

(1)查找失败的情况

查找键:25

给定列表:7个数

20

12

30

8

45

60

27

 

1.设置哨兵,即将26加到列表末尾

20

12

30

8

45

60

27

26

2.从第一个数开始比较,查找开始:

顺序查找2.png

3.利用查找器来做为末尾的标志判断,走到最后的哨兵(位置为8)7)结束查找,查找失败。

(2)查找成功的情况

查找键:8

给定列表:7个数

20

12

30

8

45

60

27

1.设置哨兵,即将8加到列表末尾

20

12

30

8

45

60

27

8

2.从第一个数开始比较,查找开始:

顺序查找3.png

3.遇到第一个8停止查找,获取8的位置为4<7,查找成功,结束。

应用2-挑出错误分类的书

案例:小红是图书馆的管理人员,每天负责将各类书分门别类的放好。小红手里有一本计算科学的书籍,已知小说类的书里混杂了各类其他书籍,小红想知道这里面有没有混杂计算机科学的书,但是不并知道书架上有多少本书。

解决步骤:

明确问题:在一堆小说类里找出计算机科学的书

  1. 把手里的那本计算科学书放到书架的最后
  2. 开始一本一本地比对,若看到第一本计算科学的书,停止查找。
  3. 判断是不是自己开始放到最后的那一本,若不是则找到被放错了的书;若是,则这堆书里没有混杂计算机的书。

可以体现的计算思维

顺序查找是把数据元素与查找键逐一进行比对,这个过程重复进行,非常适合机器完成,体现了计算思维的机械化特点。