计算基础教程 5

授课内容查找学时2教学目标知识目标理解查找的核心概念及无序、有序查找的分类掌握顺序查找的原理、实现及监视哨优化技巧掌握二分查找的核心思想及循环、递归两种实现方法了解STL中常用查找函数的基本用法及使用前提能力目标提升查找算法的逻辑分析、流程设计与优化能力培养根据数据特征选择适配查找算法的实践能力强化查找算法的应用及结合STL函数解决实际问题的能力重点与难点重点顺序查找的实现流程及监视哨的优化原理二分查找的核心逻辑及循环、递归两种实现方式二分查找中左右边界的查找方法STL中binary_search、lower_bound等查找函数的使用难点理解二分查找的区间划分逻辑及边界条件判断灵活运用不同查找算法及STL函数解决实际查找问题教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接排序算法，学习编程中常用的查找操作相关知识查找是数据处理的基础操作，在日常编程和竞赛中应用广泛掌握不同查找算法的特点，能显著提升数据查找的效率顺序、二分查找是竞赛、考级中高频考点，是后续复杂查找的基础学会使用STL查找函数，能简化编程流程，提升编程效率第二部分：新课讲解一、查找概述查找算法分为无序查找和有序查找二类。无序查找：被查找数列不需要有序（事先不需要进行排序）有序查找：被查找数列必须为有序数列（事先需要进行排序）二、顺序查找1、基本思想顺序查找属于无序查找，它不要求被查找的数列事先已排序。基本算法为：将数组中的元素逐个与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到等于k的元素，则查找失败。2、程序在有n个元素的数组a中查找值为key的元素，成功时返回找到元素的索引，失败时返回-1。intSequenceSearch(inta[],intn,intkey){ for(inti=0;i<n;i++) if(a[i]==key)returni; return-1; //查找失败}3、监视哨监视哨是一个小技巧，可以减少顺序查找中的判断次数，从而大大提高程序效率。如果要在有n个元素的数组a中查找特定值key，我们需要这样定义数组：inta[n+1]={……,key};在数组尾部增加一个元素，并且将其值设置为key，此元素就是监视哨。这样，查找过程中将一定能够查找到一个值为key的元素，因此循环过程中只需要判断“a[i]==key”即可，而不需要再判断“i<n”。当找到key后，需要判断它是否是监视哨（数组尾部额外添加的那个元素）。若是，说明原数据中没有key，应返回-1；否则说明原数据中存在key。三、二分查找1、概述二分查找（BinarySearch）也称为折半查找，它是一种效率很高的查找方法。二分查找是最典型的有序查找，即它要求数据必须事先已排序。2、二分查找算法假设序列中元素是按升序排列的，按如下步骤进行查找操作：①将序列中间位置处的元素与x（待查找值）比较，如果两者相等，则查找成功。否则，进入下一步。②利用中间位置的元素将序列分成前、后两个子序列，如果中间位置的元素大于x，则下一步在前一子序列中查找，否则下一步在后一子序列中查找。③重复以上过程，直到找到x，或者子序列为空为止。整个过程如下图：3、二分查找程序intBinSearch(inta[],intleft,intright,intkey) { if(left>right)return-1; //查找失败 intmid=left+(right-left)/2; if(a[mid]==key)returnmid; //查找成功 if(a[mid]<key) //继续在后半区间a[mid+1→right]中查找 returnBinSearch(a,mid+1,right,key); else //继续在前半区间a[left→mid-1]中查找 returnBinSearch(a,left,mid-1,key);}4、查找左右边界针对重复的元素，就存在查找左边界（第一次出现的位置）和查找右边界（最后一次出现的位置）这二种要求。以在1，3，3，3，5中查找第一个3的出现位置为例分析。只需要对基础二分查找的查找过程稍加修改即可：未找到3时的处理方法不变，在找到3时进行如下处理：如果当前元素的前一个元素小于3，或者当前元素就是第1个元素，则结束查找。否则，放弃当前元素及其之后的元素，继续在当前元素之前的区间中查找。四、STL中的查找函数1、概述STL中总共有13个查找函数，下面介绍其中最常用的3个二分查找函数：binary_search、lower_bound和upper_bound。这些函数的使用都有一个前提，那就容器内是一个非递减序列（非降序列）。2、binary_search语法：binary_search(first,last,value,比较函数)binary_search试图在已排序的[first,last)中寻找元素value。如果[first,last)内有等价于value的元素，它会返回true，否则返回false。3、lower_bound与upper_boundlower_bound与upper_bound这二个函数用于查找边界位置。lower_bound返回一个非递减序列[first,last)中的第一个大于等于val的位置，或者说在有序序列范围内可以插入指定值而不破坏容器顺序的第一个位置。upper_bound返回一个非递减序列[first,last)中第一个大于va