折半查找

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

我们想在给定的数据中找到自己想要的数据,就是查找。折半查找是一种高效、简单的查找方法,但是要求先对数据进行排序,非常适合反复多次的查找。

基本概念

首先我们队需要进行查找的数据进行从小到大的排序,然后比较查找键和中间元素,如果相等,查找结束。否则,如果查找键小于中间元素则对前半部分继续执行同样的操作,反之,若查找键大于中间元素,则对后半部分执行同样的操作。如果到了表头或是表尾都没有找到,则是查找失败。

应用范围

折半查找适用于有序集合的查找。可以用于在字典中查找单词,或是在排序好的学生名单中来查找某个学生。

使用方法及步骤

  1. 确定集合有序和查找键
  2. 将查找键与集合中间元素作比
  3. 若等于则查找成功,结束。若小于,则将比较范围限制于前半部分,重复2;若大于,则将比较范围限制于后半部分,重复2.

应用案例

应用1-数的查找

案例:在下面的数组中找出25,并返回其位置。

8

13

25

35

44

58

60

71

88

解决步骤:

  1. 上述为有序数组共9个元素,查找值为25
  2. 比较25以及第5个元素44;
  3. 缩小范围至第一个元素到第四个元素:比较25与第二个元素13,25>13,将范围转至第三个元素25:25=25,查找成功,结束。

应用2-根据学号查找学生信息

案例:老师上课的时候随机抽取学号点名让学生起来回答问题,已知班上有60个同学,怎样快速找到学号为48的同学的命名(学生信息均按学号排好序存在excel表中)

解决步骤:

  1. 已知名单表是按学号排好序的,查找第48位同学
  2. 48<30,所以第48位一定是在后半部分的名单中,将名单拉到后半部分;
  3. 在第31到第60间,48>45,所以48一定在45以后,60之前,将名单拉至这个范围;

依次重复按此方法比较,就找到48了。

注:在生活中的应用因为集合比较小,当范围缩小到比较小时,就直接利用顺序查找。

可以体现的计算思维

从上面的案例中我们可以发现,相比一个一个查找的方法,利用折半查找的方法每次查找都将范围缩小到一半,并且每次都只需要在分半后的一半内来进行操作,使得问题规模变小,所需比较的次数变少,这体现了计算思维里的规约特点。