GESP-4级-26.如何高效地查找？（课件）.pptxVIP

26.如何高效地查找？;

本章内容

介绍二分法的思想及其在检索中的应用。

介绍二分法在猜数字游戏等问题中的应用及实现。;

1.折纸和剪线

抱一的房间里挂满了地图，有世界地图、中国地图、重庆地图，有平面地图也有立体地图。抱一最喜欢研究地图，也喜欢地理知识。

抱一：致柔，你知道世界上最高的山在哪里吗？

致柔：不知道。

抱一：就在我们国家哦。世界最高峰，是珠穆朗玛峰，有8848米。最矮的山，也在我们国家哦,叫静山，只有0.6米。;

1.折纸和剪线

爸爸：假设一张纸的厚度是0.1毫米，和一张A4纸差不多厚。每对折一次，厚度翻番，也就是厚度变成2倍。假定可以无限次对折。那么这张纸对折27次就能超过珠穆朗玛峰的高度哦，你们能想象出来吗？

致柔：真的吗？

抱一：这有什么神奇的。我做过这道编程题。

爸爸：反过来，假设有一根线，长度是10000米。每次剪掉一半。假定可以剪无限次。那么，剪27次，这根线的长度就小于0.1毫米。你们能想象出来吗？

致柔：好神奇哦！

抱一：这就是我们今天要学的编程知识吗？

爸爸：差不多吧。;

2.检索

检索，即查找。假设有一个整型数组a，其元素个数为n，现在要在该数组中查找某个数num。当a中元素是无序的（即没有按从小到大或从大到小顺序排序），只能按顺序查找，当a中元素是有序的，二分查找能极大的加快查找速度。;

解题报告——顺序查找;

输入描述:

输入第一行首先是正整数n，2≤n≤10000，然后是n个整数，用空格隔开；第二行为要查找的整数num。;

样例输入1:

1035158899176018512293

18;

分析:

假设用a数组存储n个数，顺序查找的方法是，依次将num与a数组中的每个元素进行比较，如果相等，则找到；如果所有元素都比较完都还没有找到，则说明a中不存在num。这种方法查找一个数平均需要比较n/2次。如果数组中有1000000个整数，且需要在数组中反复查找，则这种方法很费时。;;

解题报告——二分查找;

假设a数组中的数已经按照从小到大的顺序排好序了（即???是初始没有排好序，在查找之前也可以做一次排序），现在要在a数组查找num。

二分查找的思想是：先将num与a数组正中的元素进行比较，如果相等，则已经找到;如果num比正中的元素还要小，则如果num存在，则肯定位于前半段，不可能位于后半段，所以不需要考虑后半段；否则，num肯定位于后半段。在前半段(或后半段)查找时，又是将num与正中的元素进行比较，…。一直到找到num，或者判断;

第1次比较时，low=0,high=9,mid=(low+high)/2=4，num的值小于a[mid]，所以如果num存在，

则必然位于前半段，将high的值更新为mid-1=3，low的值不变。

第2次比较时，low=0,high=3,mid=(low+high)/2=1，num的值大于a[mid]，所以如果num存在，则必然位于后半段，将low的值更新为mid+1=2，high的值不变。

第3次比较时，low=2,high=3,mid=(low+high)/2=2，num的值等于a[mid]。至此，查找到num。;

以上过程要用循环来实现。现在的问题是：如果num不存在，什么时候退出循环？

图1(b)以在上述数组中查找num=90的情形解释了这个问题。当第3次比较完以后，因为num的值小于a[mid]，所以如果num存在，则必然位于前半段，需要将high的值更新为mid-1=7，而low的值不变，这样highlow。这意味着num不存在，应该退出循环了。

因此，如果num不存在，退出循环的条件是：highlow。;

输入描述:

输入第一行首先是正整数n，2≤n≤10000，然后是n个整数，用空格隔开；第二行为要查找的整数num。;

样例输入1:

1015171822355160889399

18;

以下search函数实现了二分查找。在main函数中调用search函数可以实现在数组a中查找num。;

#includebits/stdc++.h

usingnamespacestd;

intsearch(inta[],intn,intnu