数据结构与算法 课件-Unit 01 二分查找

Unit01二分查找BinarySearch某个商场的柜台上，有一个价值不菲的商品不见了，是谁拿走了这件商品呢？商场视频监控是24h连续不断的，储存周期为3天。我们在视频中发现了以下几点。（1）在第一帧画面里，这件商品还在柜台上。（2）在最后一帧画面里，它不见了。如果顺序查找显然效率不高，请设计一个方法能快速找到丢失商品的关键帧。①理解和使用线性表、顺序表和数组。②认识、理解和运用顺序查找、二分查找算法。③运用大O表示法分析二分查找的时间复杂度。线性表（LinearList）线性表是n（n≥0）个具有相同特性的数据元素的有限序列，即表中的元素属于同一个数据对象，且相邻的元素之间存在着“序偶”关系。（1）元素个数n称为线性表的长度（当n=0时，称为空表）。（2）若非空线性表记为（a1,…ai-1,ai,ai+1,…,an），则当i=1时，有且仅有一个后继a2，没有前驱；当i=n时，有且仅有一个前驱an-1，没有后继；其余的所有元素ai()都有且仅有一个前驱ai-1和一个后继ai+1。线性表是最简单、最基础、最常用的一种线性结构，根据存储方式的不同可分为顺序表（SequentialList）和链表（LinkedList）。其基本的操作是插入、删除和查找。学号姓名班级成绩2020001张三1972020002李四2882020003王五392…………抽象为线性结构线性表（LinearList）线性表是n（n≥0）个具有相同特性的数据元素的有限序列，即表中的元素属于同一个数据对象，且相邻的元素之间存在着“序偶”关系。（1）元素个数n称为线性表的长度（当n=0时，称为空表）。（2）若非空线性表记为（1,…,i-1,i,i+1,…,n），则当i=1时，有且仅有一个后继a2，没有前驱；当i=n时，有且仅有一个前驱an-1，没有后继；其余的所有元素ai()都有且仅有一个前驱ai-1和一个后继ai+1。一维数组（LinearArray）数组是有序的数据元素序列。在程序设计中，数组是把具有相同类型的若干数据元素按有序的形式组织起来的一种形式。用一个统一的数组名和下标来唯一地确定数组中的数据元素，下标决定了数据元素的位置，数组中各个数据元素之间的逻辑关系由下标体现。下标的个数决定了数组的维数，下标个数是一位数的称为一维数组。二维及多维数组可以看作是一维数组的多次叠加产生的。通常使用一维数组来实现顺序表，数组的下标可以看作线性表在内存的相对地址，因此顺序表的最大特点是逻辑上相邻的两个元素在物理位置上也相邻。线性表的顺序存储结构——顺序表把线性表中的数据元素按照其逻辑次序依次存放在一组地址连续的存储单元里的方式称为线性表的顺序存储结构，采用这种存储结构的线性表称为顺序表。在程序设计中，一般用一维数组来实现。1．存储地址使用一维数组存储顺序表，意味着要分配固定长度的数组空间，因此必须确定数组的大小。一维数组a由n个数据元素组成，a[0]的存储地址为LOC(a0)，如果每个数据元素占d个存储单元，那么数组中任意数据元素a[i]的存储地址的计算公式为式（1-1）：

LOC(ai)=LOC(a0)+i×d（0≤i≤n-1） （1-1）2．顺序表的C语言类型定义#defineMAXLEN100 //顺序表大小，根据实际需要来定typedefstructSeqList{intdata[MAXLEN]; //存储线性表数据元素的数组空间

intlength;} //当前顺序表的长度或规模3．顺序表的主要特点顺序表用一维数组实现，数组的下标可以看成数据元素在内存的相对地址，因此顺序表的特点：逻辑上相邻两个数据元素在物理位置上也相邻。例题01-01求数组中数据元素的内存地址。4．在顺序表中插入（删除）数据元素如图1-1所示，要在顺序表中数组下标i的位置之前插入新数据元素A，首先要将数组下标i+1以后的所有数据元素依次向后移动一位，再在下标i的位置上插入数据元素A。同样地，若要删除顺序表中某一数据元素，则需要将该数据元素以后的所有数据元素依次向前移动一位。图1-1顺序表插入新元素的过程查找的基本概念1．查找表（SearchTable）查找表是由同一类型数据元素（或记录）构成的集合。查找表通常进行的操作如下。查询某个特定的数据元素是否在表中。检索某个特定的数据元素的各种属性。在查找表中插入一个数据元素。在查找表中删除某个数据元素。2．关键字（Key）关键字是数据元素中某个数据项的值，使用它可以标识一个数据元素。若关键字可以唯一地标识一个数据元素，则称此关键字为主关键字（PrimaryKey）；反之，则将不能唯一地标识数据元素的关键字称为次关键字（SecondaryKey）。3．查找（Searching）查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。如果表中存在这样的数据元素，则查找成功，此时查找结果为该数据元素的信息，或者指示其在查找表中的位置；若表中不存在这样的数据元素，则查找失败。4．查找分类静态查找（StaticSearch）不涉及插入和删除操作，只做查找操作的查找，查找结果不影响查找表。动态查找（DynamicSearch）涉及插入和删除操作的查找，查找结果可能会改变查找表。5．平均查找长度（AverageSearchLength）对于含有n个数据元素的查找表，当查找成功时的平均长度由式（1-2）表示： （1-2）其中，是查找第i个数据元素的概率（一般认为每个数据元素查找概率相等）；是查找第i个数据元素所需要的与关键字的比较次数。顺序查找（SequentialSearch）算法顺序查找也称为穷举查找，又叫线性查找，这是一种最基本、最简单的顺序表查找方法。它的查找过程：从顺序表的一端向另一端逐个将数据元素值与待查关键字比较，若相等，则查找成功，返回该数据元素在表中的位置；若直至最后一个数据元素也没有与之相等的数据元素，则查找失败。按照数据元素在顺序表中的次序，依次逐个访问，完成查找任务，所以其算法时间复杂度是O(n)。例题01-02在序列（8,3,10,15,4,7,11,2,12,6,14）中，采用顺序查找方法查找数据元素11和5。二分查找（BinarySearch）算法二分查找也称为折半查找，它充分利用了数据元素间的次序关系，采用分治策略，可在最坏的情况下用O(log2n)的时间复杂度完成查找任务。它是一种效率较高的查找方法。1．算法设计将n个数据元素递增（或递减）有序的顺序表存储在数组a中，取中间位置数据元素的值a[n/2]与待查的关键字x作比较。如果x<a[n/2]，那么只需在数组a的左半部分（或右半部分）继续查找x；如果x>a[n/2]，那么只需在数组a的右半部（或左半部分）继续查找x，重复以上过程，直到某个中间位置数据元素的值与待查关键值相等，找到目标，否则该顺序表中没有待查的关键字。2．限制条件 必须采用顺序存储结构。 必须按关键字大小有序排列。3．时间复杂度分析对于规模n的有序数据元素序列，按照算法思想可知每一次查找丢掉一半，另一半继续重复，操作数据元素的个数变化是n,n/21,n/22,…,n/2k，其中k就是循环的次数。由于n/2k取整后≥1，即令n/2k=1，得k=log2n。所以，时间复杂度可以由式（1-3）表示：

O(n)=O(log2n) （1-3）快递公司接收的邮件按照编号递增有序存放，邮件编号唯一，可以用顺序表表示{002,003,004,006,007,008,010,011,012,014,015}。请设计程序，完成查找某一编号邮件的任务。输入要求：键盘输入查找目标。输出要求：（1）若没有找到，则输出“查无此邮件”；（2）若找到，则输出它的位置，即数组的下标。算法分析（1）查找target=5的图示分析，如右图1-2所示。算法分析（2）查找target=11的图示分析，如图1-3所示。1、根据任务要求和算法分析设计程序2、编码、调试、运行。3、做好记录。4、总结。二分查找的速度比简单查找快得多O(log2n)比O(n)快。需要搜索的元素越多（n越大），快的越多。算法运行时间并不以秒为单位算法运行时间是从其增速的角度度量的算法运行时间用大O表示法表示单元数据结构算法讲解实操01线性表顺序表数组顺序查找二分查找二分查找02顺序表数组链表简单选择排序简单选择排序03线性表顺序表链表栈递归算法递归算法04线性表顺序表数组链表快速排序快速排序05线性表顺序表数组链表散列表散列表查找算法散列表查找06顺序表链表数组串堆

BF算法KMP