《一维搜索方法》课件.pptx

一维搜索方法目录CONTENTS一维搜索方法概述线性搜索二分搜索黄金分割搜索抛物线搜索01一维搜索方法概述定义与特点定义一维搜索方法是指在单变量空间中寻找目标值或最优解的方法。特点一维搜索方法通常用于求解单变量函数的最值问题，具有简单、直观的特点，但也可能面临局部最优解的问题。二分搜索将搜索区间不断二分，通过比较中间值与目标值的差异来缩小搜索范围，适用于有序区间内的目标值查找。线性搜索通过线性逼近的方式逐步逼近目标值，适用于连续、可微的单峰函数。黄金分割法通过黄金分割点将搜索区间划分为两个子区间，再根据目标值与黄金分割点的关系来决定下一步的搜索方向，适用于连续、可微的单峰函数。常用的一维搜索方法解决实际问题一维搜索方法广泛应用于各种实际问题中，如参数优化、函数逼近、插值等。算法基础一维搜索方法是许多算法的基础，如梯度下降法、牛顿法等都需要用到一维搜索方法来寻找迭代步长。理论分析一维搜索方法在数学分析中也有重要应用，如中值定理、单调函数性质等都需要用到一维搜索方法。一维搜索方法的重要性02线性搜索线性搜索的定义线性搜索是一种基本的搜索算法，它从列表的第一个元素开始，逐个检查每个元素，直到找到目标元素或遍历完整个列表。在线性搜索过程中，我们假设列表中的元素是按顺序排列的，并且我们不知道目标元素的确切位置，只知道它存在于列表中。选择一个起始位置，通常为列表的第一个元素。初始化查看当前位置的元素是否为目标元素。检查当前元素如果当前元素不是目标元素，则将当前位置移动到下一个元素。移动到下一个元素线性搜索的步骤线性搜索的时间复杂度为O(n)，因为它需要遍历整个列表来找到目标元素。在最坏的情况下，如果目标元素不在列表中，则线性搜索需要检查列表中的每个元素。线性搜索的时间复杂度03二分搜索二分搜索是一种在有序数组中查找特定元素的搜索算法。总结词二分搜索的基本思想是将数组分为两半，比较中间元素与目标值，如果目标值与中间元素相等，则搜索成功；如果目标值小于中间元素，则在左半部分继续搜索；如果目标值大于中间元素，则在右半部分继续搜索。重复这个过程，直到找到目标值或搜索区间为空。详细描述二分搜索的定义二分搜索的步骤总结词：二分搜索的步骤包括定义搜索区间、比较中间元素和目标值、更新搜索区间等。二分搜索的步骤01详细描述021.定义初始搜索区间为整个有序数组。2.计算中间元素的索引，可以通过取整的方式得到。03二分搜索的步骤3.比较中间元素与目标值，如果相等，则搜索成功。5.如果目标值大于中间元素，则将搜索区间更新为右半部分。4.如果目标值小于中间元素，则将搜索区间更新为左半部分。6.重复步骤2-5，直到搜索区间为空或找到目标值。总结词二分搜索的时间复杂度为O(logn)，其中n为数组长度。详细描述每次循环都将搜索区间减半，因此需要logn次循环才能找到目标值或确定目标值不存在。在最坏情况下，即目标值不存在于数组中，二分搜索的时间复杂度仍为O(logn)。二分搜索的时间复杂度04黄金分割搜索黄金分割搜索的定义黄金分割搜索是一种一维搜索算法，它通过将搜索区间不断二分来寻找目标值。它利用了黄金分割的思想，即每次将搜索区间一分为二，然后根据目标值所在的区间进行下一次搜索。重复重复步骤2和3，直到找到目标值或搜索区间长度小于某个预设的阈值。初始化设置初始搜索区间为整个数据范围，并设置初始步长为数据范围的1/4。二分搜索将搜索区间不断二分，每次取区间的中点作为猜测值。判断如果猜测值等于目标值，则搜索结束；否则，根据目标值与猜测值的比较结果，将非目标值的区间缩短一半，并继续进行下一轮二分搜索。黄金分割搜索的步骤黄金分割搜索的时间复杂度为O(logn)，其中n为数据范围。因为每次都将搜索区间长度减半，所以需要进行多次二分搜索才能找到目标值。与线性搜索和二分搜索相比，黄金分割搜索在数据范围较大时具有更高的效率。黄金分割搜索的时间复杂度05抛物线搜索抛物线搜索是一种一维搜索算法，用于在有序数组中查找特定元素。它通过比较目标值与数组中间元素的差值，决定下一步搜索的方向，从而缩小搜索范围。抛物线搜索基于二分搜索的思想，但不受二分搜索的限制，可以在任意位置开始搜索。抛物线搜索的定义抛物线搜索的步骤0102032.计算当前区间的中间元素。3.比较中间元素与目标值1.初始化当前搜索区间为整个数组。02030401抛物线搜索的步骤如果中间元素等于目标值，返回该位置。如果目标值小于中间元素，将左半部分区间作为新的当前区间。如果目标值大于中间元素，将右半部分区间作为新的当前区间。4.重复步骤2和3，直到找到目标值或当前区间为空。最坏情况下，抛物线搜索的时间复杂度为O(n)，其中n为数组长度。平均情况下，由于每次比较都可以将搜索区间缩小一半，因此时间复杂度为O(logn)。抛物线搜索的时间复杂度THANKSTHANKYOUFORYOURWATCHING