《计算机算法通俗教程》课件 王丰 第1-7章 算法基础 - 贪心算法

本章导读在本章中，我们将一起探索算法的基本概念、特征、设计方法以及如何评价一个算法的优劣。同时，我们会简要介绍实现算法的编程语言和开发环境。希望通过本章的学习，大家能对算法有一个清晰的认识，并为后续的深入学习打下坚实的基础。第1章算法基础1.1算法概述1.2算法设计与描述1.3算法评价1.4编程语言与编程环境目录什么是算法？算法是解决特定问题的一系列明确、有限的步骤，是计算机解决问题的核心方案。核心属性：1.强调“步骤”而非最终的“答案”，是达成目标的过程。2.具有针对性：一个问题可以有多种不同的算法来解决。1.1.1算法的概念1.1.2算法的特征输入性：0个或多个输入，部分输入可嵌入算法。输出性：至少1个输出，无输出的算法无意义。确定性：步骤定义明确，相同输入必得相同输出。有穷性：有限步骤结束，每步有限时间完成。可行性：操作可通过基本运算有限次实现。1.1.3学好算法很重要●解决实际问题的能力电商推荐、社交排序、导航路径规划等。●培养计算思维抽象问题、逻辑严谨、权衡取舍。●应对大规模数据高效算法是处理海量数据的关键。算法应用的三大核心维度1.2.1算法设计1.理解问题：明确问题要求和输入输出。2.预测输入：考虑合法和非法输入，确保算法健壮性。3.确定数据结构：选择合适的数据组织方式。4.设计并描述算法：核心步骤，选择合适的描述方法。1.2.2算法描述（自然语言）优点：简单易懂，适合描述简单算法，便于非专业人员理解算法逻辑。缺点：不够严谨，容易产生歧义；冗长且难以描述复杂逻辑，无法直接转化为计算机程序。案例：描述“求两个正整数的最大公约数”：1.输入两个正整数m和n；2.计算r=m%n（m除以n的余数）；3.若r等于0，则n即为最大公约数，算法结束；4.否则，令m=n，n=r，返回步骤2继续执行。1.2.2算法描述（流程图）一、流程图的特点优点：简洁明了，逻辑结构清晰，分支循环一目了然，能直观展示算法执行步骤。缺点：绘制复杂，修改不便，当算法逻辑过于复杂时，图形会变得庞大且难以维护。二、应用案例右图展示了经典的“求最大公约数”算法的流程图实现。求最大公约数算法流程图核心优势：介于自然语言和编程语言之间，书写灵活、描述能力强，是算法描述的最常用方式。主要局限：没有统一的官方标准，不同的书籍或资料可能采用不同的书写格式和语法约定。应用案例：展示“求最大公约数”的伪代码逻辑，清晰描述算法步骤。//示例逻辑1.输入两个数a,b2.Whileb≠03.r=a%b4.a=b,b=r5.输出a算法评价核心逻辑设计出的算法需要通过分析评价判断其实用价值，核心评价指标主要包含以下两个方面：1.时间复杂度：用于衡量算法运行过程中时间资源的消耗情况，反映算法执行的快慢效率。2.空间复杂度：用于衡量算法运行过程中内存空间资源的消耗情况，反映算法对内存的占用程度。1.3.1算法评价指标1.3.2时间复杂度【概念】衡量算法运行时间随输入规模增长的变化趋势，分析操作次数的增长级别。【表示方法】大O表示法（O），表示最坏情况的时间性能。【计算方法】忽略低阶项和常数系数，如T(n)=3n²+2n+1的时间复杂度为O(n²)。【效率对比】O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)。不同时间复杂度的效率对比算法性能评估的重要指标1.3.3空间复杂度概念定义衡量算法运行过程中临时占用存储空间的大小随输入规模增长的趋势。通常关注算法本身额外占用的空间。表示方法与时间复杂度一致，使用大O表示法来描述空间增长的量级。典型案例：递归算法递归算法的空间复杂度主要取决于递归调用栈的深度。例如，阶乘递归的空间复杂度为O(n)。1.4编程语言与编程环境编程语言选择：C++本书选用C++作为教学语言，原因在于其语法简洁、执行效率高且在算法竞赛中普及度极高。需要强调的是，算法逻辑本身独立于具体的编程语言，任何语言均可实现算法思想，C++是实现高效算法的优选工具。推荐环境：Dev-C++推荐初学者使用Dev-C++，它免费、轻量且安装简单，无需复杂配置。主要操作包括：新建源文件、编写代码、编译运行程序以及查看报错信息进行调试，是入门算法编程的理想工具。课堂小结1.算法概念与特征：明确算法的定义，掌握算法的五大基本特征（输入、输出、有穷性、确定性、可行性）。2.算法设计与描述：学习算法设计的基本步骤，熟练运用自然语言、流程图和伪代码三种方式描述算法逻辑。3.算法评价：理解算法效率的衡量标准，重点掌握时间复杂度和空间复杂度的分析方法。4.编程语言与环境：熟悉C++语言基础，掌握Dev-C++开发环境的配置与使用，为后续编程实现打下基础。简单算法在本章中，我们将学习一些经典且实用的基础算法，包括数字的分离与合成、素数判断、最大公约数求解以及如何巧妙地运用数组下标。这些算法是编程的基石，掌握它们对于理解更复杂的算法逻辑至关重要。希望大家能认真练习，深入理解算法背后的数学思想与逻辑。第2章简单算法2.1数字分离与合成2.2素数判断2.3最大公约数2.4巧用数组下标目录1.整除运算（/）对整数进行除法，结果无小数部分。例如：5/2=2。2.模除运算（%）求余数。例如：5%2=1。3.核心逻辑通过整除和模除组合，分离数字的每一位。2.1.1数字分离inti=123,a,b,c;a=i%10; //提取个位c=i/100; //提取百位b=i%100/10;//提取十位数字合成：将各位数字合并成一个整数，核心算法是((0*10+1)*10+2)*10+3。计数问题：统计数字x在1到n中出现的次数，核心是循环分离每一位并计数。核心代码如下//计数问题核心代码片段for(inti=1;i<=n;i++){ intb=i; while(b!=0)

{ if(b%10==x)t++; b=b/10; }}2.1.2数字合成&2.1.3计数问题1.素数定义与判断方法定义：大于1的自然数，除了1和自身外，不能被其他自然数整除。方法：让n除以2到√n之间的每一个数，若均不能整除则为素数。intisPrime(intn){intk=sqrt(n),i;for(i=2;i<=k;i++)

if(n%i==0)break;//循环判断returni>k;//返回判断结果}2.2.1素数及其判断2.2.2批量求素数（埃氏筛选法）算法思想：先假设所有数都是素数，然后逐步排除合数。核心步骤：从2开始，将每个素数的所有倍数标记为合数。代码实现：//埃氏筛选法核心代码片段for(inti=2;i<=k;i++){ if(!a[i])continue; for(intj=2;j<=n/i;j++) a[i*j]=false;}图2-1埃氏筛选法执行过程示意图总结：该算法通过“空间换时间”的策略，高效地将合数筛选出来。2.3.1最大公约数概念最大公约数（GCD）是数论中的重要概念，指两个或多个整数共有约数中最大的一个。理解其定义并掌握欧几里得算法等高效求解方法。定义：几个整数公有的约数，称为这几个数的公约数。公约数核心概念：在所有公约数中数值最大的那一个，即为最大公约数。最大公约数实例演示：整数12和16的公约数有1、2、4，其中最大公约数是4。示例：12&162.3.2辗转相除法▍算法步骤：用二数相除得到余数，再用除数和余数重复此过程，直到余数为0，最后的除数就是最大公约数。▍核心代码（C++）：r=m%n;while(r!=0){

m=n;

n=r;

r=m%n;}cout<<n<<endl;图2-3辗转相除法流程示意图技巧核心：利用数组的下标来表示一项信息（例如学生的学号），而数组元素对应的值则用来存储另一项关联信息（例如该学生的成绩）。核心优势：这种方法充分利用了数组的随机访问特性，可以实现数据的快速查找和高效统计，避免了繁琐的遍历匹配过程。典型应用：经典算法如“筛选法求素数以及“桶排序等，均是此技巧的经典实践。2.4.1巧用数组下标桶排序核心原理与代码实现2.4.2桶排序(1)算法思想将数据分配到有限数量的“桶”里，最后按顺序合并所有桶内数据，完成整体排序。(2)核心代码(C++)//初始化桶并分配数据for(inti=1;i<=n;i++)

{cin>>x;a[x]++;}//遍历桶输出结果for(inti=0;i<10;i++)

for(intj=0;j<a[i];j++)

cout<<i<<"";课堂小结●数字处理：掌握了数字分离与合成的基本方法，能够处理复杂的数值运算。●素数问题：学会了素数判断和埃氏筛选法批量求素数，提升了算法效率。●最大公约数：掌握了高效的辗转相除法，解决了数论中的经典问题。●编程技巧：理解了巧用数组下标的思想，并学习了桶排序算法。3.1枚举法概述3.2枚举法实例-3.2.1百钱买百鸡-3.2.2火柴棒等式目录3.1枚举法概述枚举法，也叫穷举法，是一种非常基础但实用的算法思想。它的核心思想是在可能的解空间中逐一列举所有可能的候选解，并逐一验证是否符合问题的条件。虽然枚举法在某些情况下效率可能不高，但对于小规模数据或作为优化算法的基础，它是不可或缺的。本章我们将学习枚举法的基本概念，并通过经典案例掌握其应用与剪枝优化技巧。3.1算法基础核心思想：将所有可能的解逐一代入问题中进行验证，满足所有限定条件的解即为正确解。核心思想适用场景：解的范围已知且有限，无明显规律可循的问题。例如密码破解、组合问题等。适用场景特点：效率不高，但实用有效。依赖计算机强大的计算能力来弥补算法本身的低效。特点3.1枚举法概述题目描述鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？人工分析思路设鸡翁为x，鸡母为y，鸡雏为z，建立二元一次方程组进行求解。计算机枚举思路确定变量取值范围，逐一验证是否满足方程条件：鸡翁x范围：0~20鸡母y范围：0~33鸡雏z范围：0~3003.2.1百钱买百鸡（题目与分析）3.2.1百钱买百鸡（程序实现）优化思路：利用总数为100的条件，将三重循环优化为双重循环。确定鸡翁(x)和鸡母(y)数量后，鸡雏(z)数量可由z=100-x-y直接得出。关键点：判断条件中需包含z%3==0，确保鸡雏数量是3的倍数。for(x=0;x<=100/5;x++)//列举鸡翁的所有可能取值for(y=0;y<=100/3;y++) //列举鸡母的所有可能取值

{z=100-x-y;//根据x，y计算鸡雏的数量

if(5*x+3*y+z/3==100&&z%3==0)//找到一组正确答案

cout<<x<<""<<y<<""<<z<<endl;}3.2.2火柴棒等式（题目与分析）【题目描述】用n根火柴棒拼出形如A+B=C的等式，火柴棒必须全部用完。【分析思路】1.计算每个数字所需的火柴棒数量。2.枚举A和B的可能值，计算C=A+B。3.验证拼出A、B、C及符号所需的火柴棒总数是否等于n。【取值范围】A、B不超过1000。图3-1火柴棒数字拼法示意图核心函数：Num(x)计算拼出数字x所需的火柴棒数量，支持多位数拆分计算。intNum(intx){if(x<10)returna[x];intsum=0;while(x>0){sum+=a[x%10];x/=10;}returnsum;}主逻辑：枚举验证枚举A和B的所有可能值，计算C=A+B，验证火柴棒总数是否符合要求。for(inti=0;i<=1000;i++)for(intj=0;j<=1000;j++)if(Num(i)+Num(j)+Num(i+j)==n-4)ans++;3.2.2火柴棒等式（程序实现）枚举法优化思路1.缩小枚举范围：根据问题条件，合理估计变量的最大和最小值，避免无效的遍历。2.减少枚举变量：利用问题中的等式关系，用其他变量表示某些变量，从而减少循环层数。3.提前终止：在循环内部设置条件判断，一旦找到解或确定无解，立即终止循环。课堂小结枚举法思想：穷举所有可能解，逐一验证条件。这是最基础的算法设计思路，虽然简单但应用广泛。经典实例：掌握了“百钱买百鸡”和“火柴棒等式”的求解方法，理解了如何将实际问题转化为循环验证问题。优化策略：学会了缩小范围、减少变量、提前终止等优化技巧，以提高程序运行效率，避免不必要的计算。4.1递归概述4.2Fibonacci数列4.3其它典型题目-4.3.1Hanoi塔问题-4.3.2数的计算第4章递归4.1递归的概念与应用递归是一种非常重要的算法思想，它不仅是一种编程技巧，更是一种解决问题的思维方式。在本章中，我们将深入学习递归的基本概念，并通过几个经典的例子来掌握它的应用和优化方法。递归通过将复杂问题分解为更小的、相似的子问题来解决。理解递归的核心在于找出递归关系和递归终止条件，这是编写高效递归代码的关键。第4章递归4.1递归概述递归是一种强大的算法设计思想，通过将复杂问题分解为更小的子问题来求解。理解递归的关键在于掌握其“递推”与“回归”的过程。核心思想：将复杂问题分解为简单的子问题，直到子问题可直接求解，再回溯得到原问题的解。核心思想工作流程：包含“递推”（将问题分解为子问题）和“回归”（从子问题回溯求解）两个过程。工作流程典型应用：1.问题定义递归（如阶乘、斐波那契）2.数据结构递归（如树、文件夹）3.问题解法递归（如汉诺塔）典型应用1)定义F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2)。从第三项开始，每一项都是前两项之和。2)递归求解代码利用递归思想实现的C++代码如下：4.2.1Fibonacci数列概述intfib(inti)//返回第i项的值{if(i==0)return0;if(i==1) return1;returnfib(i-2)+fib(i-1);}4.2.2消除重复求解（备忘录）1.问题分析原始递归解法会导致大量的重复计算，随着n的增大，时间复杂度呈指数级增长，效率极其低下。2.解决方案：备忘录法引入“备忘录”（通常是数组或哈希表），将已经计算过的子问题结果存储起来。当再次需要该结果时，直接从备忘录中读取，避免重复递归计算。inta[100]={0,1};//备忘录数组intfib(inti){if(a[i]>0||i==0)

returna[i];a[i]=fib(i-1)+fib(i-2);returna[i];}图4-2斐波那契数列递归求解的重复计算示意与优化代码问题描述：将n个圆盘从A柱移到C柱，每次只能移动一个，且不能将大盘放在小盘上移动规则：一次只能移一个圆盘。圆盘只能在三根柱子间移动。任何时刻，大盘不能放在小盘之上。图4-3-1Hanoi塔初始状态图4.3.1Hanoi塔问题递归思想：要移动n个盘子，可以分解为三个步骤：1.将n-1个盘子从A柱移到B柱（以C柱为辅助）。2.将第n个盘子从A柱移到C柱。3.将n-1个盘子从B柱移到C柱（以A柱为辅助）。核心：将移动n个盘子的问题，转化为移动n-1个盘子的子问题。算法分析核心代码：递归函数move实现移动逻辑。voidmove(intn,chara,charc,charb){if(n==0)return;move(n-1,a,b,c);//把n-1个盘子从a移到b，用c做辅助cout<<++k<<":"<<a<<"→"<<c<<endl;//移动第n个盘子move(n-1,b,c,a);//把n-1个盘子从b移到c，用a做辅助}参数说明：n：盘子数量，a：源柱子，c：目标柱子，b：辅助柱子4.3.1Hanoi塔问题（程序实现）4.3.2数的计算（题目与分析）题目规则：找出满足特定规则的数的个数。规则是在数的左边添加不超过其一半的自然数，且该过程可递归进行。题目描述递归分析：设f(n)为n能扩展出的数的个数，则递推公式为：f(n)=1+f(1)+...+f(n/2)其中，“1”代表数n本身。算法分析优化问题：在直接递归求解过程中，会存在大量重复计算子问题的情况，导致效率低下。解决：需引入“备忘录”技术进行剪枝优化。优化策略4.3.2数的计算（程序实现）inta[1001];//备忘录数组intdfs(intm){//递归函数定义if(a[m]>0)returna[m];//记忆化搜索a[m]=1;//包含自身for(inti=1;i<=m/2;i++)//枚举左加数a[m]+=dfs(i);//累加结果returna[m];//返回总数}//函数结束课堂小结核心知识回顾递归思想：将复杂问题逐步分解为规模更小的子问题，通过递归调用自身求解，最终合并子问题答案得到原问题解。经典实例：斐波那契数列、汉诺塔问题、数的计算等，这些问题均具有明显的重复子问题特征。优化技巧：递归算法常存在大量重复计算，可使用“备忘录”技术（如哈希表、数组缓存）存储已计算结果，以空间换时间，将时间复杂度从指数级降低至线性级。目录5.1排序问题概述5.2冒泡排序5.3选择排序5.4快速排序5.5其它排序算法简介5.1排序算法概述排序是计算机科学中最基础、最常用的算法之一，在我们的日常生活中也无处不在。它不仅是数据处理的基础，也是许多复杂算法的核心组成部分。在本章中，我们将深入学习几种经典的排序算法，包括冒泡排序、选择排序和快速排序。我们将逐一分析它们的基本原理、时间复杂度、空间复杂度以及各自的适用场景，帮助大家建立起对算法效率的直观认识。第5章排序定义：将数据按规则重排。常见算法：冒泡、选择、快速、插入、希尔、归并、堆排序等。比较排序：比大小定次序，下界O(nlogn)。非比较排序：利用数据特性，可达O(n)，需额外空间。稳定性定义：稳定：相等元素相对顺序不变。不稳定：不保证相对顺序。（3）算法稳定性5.1排序问题概述5.2.1冒泡排序原理核心思想：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。执行过程：每一趟冒泡都会将当前未排序区的最大值“冒泡”到未排序区的末尾。算法特点：n个数据需要进行n-1趟冒泡，每趟比较次数递减。核心代码：通过两层循环实现，外层循环控制趟数，内层循环进行相邻元素的比较与交换。for(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++)

{if(a[j]>a[j+1])swap(a[j],a[j+1]);}}算法说明：1.时间复杂度为O(n²)，属于稳定排序算法。2.优化策略：可通过设置标志位，若某一趟未发生交换则说明已有序，提前退出循环。5.2.2冒泡排序程序5.2.3车厢重组（冒泡排序应用）问题描述：通过旋转桥交换相邻车厢，求将车厢按编号排序的最少旋转次数。算法分析：问题本质就是统计冒泡排序过程中发生交换操作的次数。通过引入计数器并利用提前退出机制可优化效率。for(inti=0;i<n-1;i++){boolok=true;for(intj=0;j<n-1-i;j++){if(a[j]>a[j+1]){swap(a[j],a[j+1]);count++;ok=false;}}if(ok)break;//提前退出优化}5.3.1选择排序原理核心思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。（1）核心思想排序过程：1.从未排序区找到最小元素。2.将其与未排序区的第一个元素交换。3.缩小未排序区，重复上述步骤。（2）排序过程算法特点：交换次数比冒泡排序少，但无法提前退出，时间复杂度为O(n²)。（3）算法特点5.3.2选择排序程序核心思想：外层循环遍历每个位置，内层循环寻找最小值的下标，最后进行交换。算法特性：时间复杂度为O(n²)，是不稳定排序算法。for(inti=0;i<n-1;i++)

//进行n-1轮选择{intk=i; //最小元素的下标

for(intj=i+1;j<n;j++) //在当前无序区a[i]..a[n-1]中选最小的元素a[k]

if(a[j]<a[k])k=j;if(k!=i)swap(a[i],a[k]); //交换a[i]和a[k]，将当前最小值放到a[i]位置}5.4.1快速排序原理核心思想：采用分治思想。选择一个基准值，将数据分为两部分，左边小于基准值，右边大于基准值，然后递归处理两部分。执行过程：1.选择基准值；2.分区操作（小左大右）；3.递归排序左右子数组。算法特点：平均时间复杂度为O(nlogn)，最坏情况O(n²)，属于不稳定排序。图5-8快速排序分区与归位过程示意图核心代码（递归实现）：voidquick_sort(inta[],intleft,intright){if(left>=right)return;intL=left,R=right,key=a[L];while(L<R)

{while(L<R&&a[R]>=key)R--;while(L<R&&a[L]<=key)L++;if(L<R)swap(a[L],a[R]);}swap(a[left],a[L]);quick_sort(a,left,L-1);quick_sort(a,R+1,right);}5.4.2快速排序程序问题描述：找出数列排序后的第k小的数。算法分析：利用快速排序的分区思想，只需递归处理第k个数所在的子数组，无需完全排序。核心优化：在递归前判断第k个数是否在当前区间内，不在则直接返回，避免无效递归。5.4.3第k小整数（快速排序应用）if(left>k||right<k)return;//关键优化：提前终止5.5.1插入排序简介核心思想：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。核心思想生活类比：如同打牌时抓牌，每抓一张就插入到手中合适的位置，保持手牌有序。生活类比算法特点：简单直观，对基本有序的数据效率较高；时间复杂度O(n²)，属于稳定排序算法。算法特点排序算法对比算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(nlogn)O(n²)O(logn)不稳定插入排序O(n²)O(n²)O(1)稳定冒泡排序：相邻比较交换，稳定，可提前退出。选择排序：选择最小元素交换，不稳定，交换次数少。快速排序：分治思想，效率高，平均O(nlogn)，不稳定。排序算法选择：根据数据规模、有序程度和稳定性要求综合考虑。算法设计的核心在于平衡时间复杂度与空间复杂度，选择最适合场景的策略。目录6.1查找概述6.2顺序查找6.3二分查找6.4STL中的查找函数6.1查找概述查找是计算机编程中最基本、最常用的操作之一，我们每天都在使用它，比如在通讯录里找联系人，在文件系统中找文件。在本章中，我们将学习几种经典的查找算法，包括顺序查找和二分查找，并了解如何利用C++标准库中的查找函数来提高编程效率。第6章查找定义：在大量信息中寻找特定元素的过程。基本定义常见算法：1.顺序查找2.二分查找3.插值查找4.哈希查找等常见算法分类：无序查找：数列无需有序（如顺序查找）。有序查找：数列必须有序（如二分查找）。算法分类6.1查找概述6.2.1顺序查找基础一、基本思想逐个比较数组元素与目标值，找到则返回索引，否则返回-1。二、性能分析•时间复杂度：O(n)•最好情况：1次比较•最坏情况：n次比较•平均情况：(n+1)/2次比较三、核心代码实现intSequenceSearch(inta[],intn,intkey){for(inti=0;i<n;i++)if(a[i]==key)returni;return-1;}监视哨技术核心思想在数组末尾添加一个等于目标值的“监视哨”，避免每次循环都检查数组是否越界，将两次判断合并为一次。操作步骤1.将目标值存入数组末尾。2.从数组头部开始查找，找到目标值即停止。3.判断位置，若是末尾则说明原数组无目标值。代码优化点在循环中只需判断元素是否相等，无需判断索引是否越界。从而减少了一半的比较次数，提高了查找效率。优化代码通过引入监视哨，我们将原本在循环中需要进行的“索引越界检查”和“目标值比较”这两个操作，简化为了单一的“目标值比较”。这种优化在数据量较大时能显著减少CPU的指令执行次数，从而提升算法效率。6.3.1二分查找概述一、基本思想利用分治思想，在有序数组中，通过不断将查找区间减半来快速定位目标值。二、适用条件待查找的数据序列必须是有序的（升序或降序）。三、查找步骤取中间位置元素与目标值比较；若相等则查找成功；若目标值更小，在左半区间继续查找；若更大，在右半区间继续查找；重复步骤，直到找到目标值或区间为空（查找失败）。图6-1二分查找过程示意图一、核心代码（C++实现）intBinSearch(inta[],intn,intkey){intleft=0,right=n-1;while(left<=right){intmid=(left+right)/2;if(a[mid]==key)

returnmid;elseif(a[mid]<key)

left=mid+1;else

right=mid-1;}return-1;}6.3.2二分查找程序（循环法）二、性能分析二分查找每次比较都将查找区间缩小一半，时间复杂度为O(logn)，在数据量较大时，查找效率远优于顺序查找（O(n)）。6.3.2二分查找程序（递归法）算法思想：递归法将查找问题分解为更小的子问题，直到规模缩小到可直接解决。代码简洁，但性能略逊于循环法，且存在栈溢出风险。intBinSearch(inta[],intleft,intright,intkey){if(left>right)return-1;//递归终止条件intmid=left+(right-left)/2;if(a[mid]==key)

returnmid;elseif(a[mid]<key)returnBinSearch(a,mid+1,right,key);elsereturnBinSearch(a,left,mid-1,key);}6.3.3查找左右边界1.问题描述在有序数组中存在重复元素时，需要查找目标值第一次出现（左边界）或最后一次出现（右边界）的位置。2.算法思路基于二分查找框架，当找到目标值时不立即返回。查找左边界时，收缩右边界继续向左搜索；查找右边界时，收缩左边界继续向右搜索。直到区间无效，最终确定边界位置。3.核心代码逻辑(查找左边界)intleft_bound(int[]nums,inttarget){...if(nums[mid]==target)

right=mid-1;...}6.4.1STL查找概述概述：C++标准模板库（STL）提供了丰富的查找函数，无需手动实现。binary_search功能：判断指定元素是否存在于有序区间中。返回值：存在返回true，否则返回false。存在性判断lower_bound功能：查找第一个大于等于目标值的元素。返回值：指向该元素的迭代器。查找下界upper_bound功能：查找第一个大于目标值的元素。返回值：指向该元素的迭代器。查找上界【功能描述】在有序区间内查找目标值是否存在。该函数不返回具体位置，仅判断存在性。【函数语法】

binary_search(first,last,value)【返回值】布尔值（bool）：找到返回true，未找到返回false。【示例代码】

vector<int>v={1,3,5,7,9};boolfound=binary_search(v.begin(),v.end(),5);//found=true6.4.2binary_search函数lower_bound函数：返回容器中第一个大于等于目标值的元素位置。upper_bound函数：返回容器中第一个大于目标值的元素位置。返回值类型：迭代器（对于普通数组则是指针），指向找到的边界位置。核心用途：在有序序列中高效查找元素的插入点或边界，时间复杂度为O(logn)。6.4.3lower_bound与upper_bound函数图6-4lower_bound与upper_bound返回值示意图课堂小结●顺序查找：简单直观，适用于无序数据，时间复杂度O(n)，可通过监视哨优化。●二分查找：效率高，时间复杂度O(logn)，要求数据有序，有循环和递归两种实现方式。●STL查找函数：高效便捷，包括binary_search、lower_bound和upper_bound，是实际开发的首选。●算法选择：根据数据是否有序、数据规模和开发效率综合考虑。目录7.1贪心算法概述7.2典型例题7.1贪心算法贪心算法是一种非常重要且常用的算法思想，它通过在每一步都做出局部最优的选择，来期望最终得到全局最优解。在许多经典问题中，如最短路径、最小生成树等，它是高效且正确的。在本章中，我们将深入探讨贪心算法的基本概念、核心性质（贪心选择性质与最优子结构性质），并通过最优装载、活动选择等典型例题来掌握其实际应用。7.1贪心算法定义：所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。含义：每一步的贪心选择都必须是最终最优解的一部分，即每一步都做出当前看似最好的