《一維搜索方法》課件

一維搜索方法目錄CONTENTS一維搜索方法概述線性搜索二分搜索黃金分割搜索拋物線搜索01一維搜索方法概述定義與特點定義一維搜索方法是指在單變量空間中尋找目標值或最優(yōu)解的方法。特點一維搜索方法通常用于求解單變量函數(shù)的最值問題，具有簡單、直觀的特點，但也可能面臨局部最優(yōu)解的問題。二分搜索將搜索區(qū)間不斷二分，通過比較中間值與目標值的差異來縮小搜索范圍，適用于有序區(qū)間內的目標值查找。線性搜索通過線性逼近的方式逐步逼近目標值，適用于連續(xù)、可微的單峰函數(shù)。黃金分割法通過黃金分割點將搜索區(qū)間劃分為兩個子區(qū)間，再根據(jù)目標值與黃金分割點的關系來決定下一步的搜索方向，適用于連續(xù)、可微的單峰函數(shù)。常用的一維搜索方法解決實際問題一維搜索方法廣泛應用于各種實際問題中，如參數(shù)優(yōu)化、函數(shù)逼近、插值等。算法基礎一維搜索方法是許多算法的基礎，如梯度下降法、牛頓法等都需要用到一維搜索方法來尋找迭代步長。理論分析一維搜索方法在數(shù)學分析中也有重要應用，如中值定理、單調函數(shù)性質等都需要用到一維搜索方法。一維搜索方法的重要性02線性搜索線性搜索的定義線性搜索是一種基本的搜索算法，它從列表的第一個元素開始，逐個檢查每個元素，直到找到目標元素或遍歷完整個列表。在線性搜索過程中，我們假設列表中的元素是按順序排列的，并且我們不知道目標元素的確切位置，只知道它存在于列表中。選擇一個起始位置，通常為列表的第一個元素。初始化查看當前位置的元素是否為目標元素。檢查當前元素如果當前元素不是目標元素，則將當前位置移動到下一個元素。移動到下一個元素線性搜索的步驟線性搜索的時間復雜度為O(n)，因為它需要遍歷整個列表來找到目標元素。在最壞的情況下，如果目標元素不在列表中，則線性搜索需要檢查列表中的每個元素。線性搜索的時間復雜度03二分搜索二分搜索是一種在有序數(shù)組中查找特定元素的搜索算法?？偨Y詞二分搜索的基本思想是將數(shù)組分為兩半，比較中間元素與目標值，如果目標值與中間元素相等，則搜索成功；如果目標值小于中間元素，則在左半部分繼續(xù)搜索；如果目標值大于中間元素，則在右半部分繼續(xù)搜索。重復這個過程，直到找到目標值或搜索區(qū)間為空。詳細描述二分搜索的定義二分搜索的步驟總結詞：二分搜索的步驟包括定義搜索區(qū)間、比較中間元素和目標值、更新搜索區(qū)間等。二分搜索的步驟01詳細描述021.定義初始搜索區(qū)間為整個有序數(shù)組。2.計算中間元素的索引，可以通過取整的方式得到。03二分搜索的步驟3.比較中間元素與目標值，如果相等，則搜索成功。5.如果目標值大于中間元素，則將搜索區(qū)間更新為右半部分。4.如果目標值小于中間元素，則將搜索區(qū)間更新為左半部分。6.重復步驟2-5，直到搜索區(qū)間為空或找到目標值?？偨Y詞二分搜索的時間復雜度為O(logn)，其中n為數(shù)組長度。詳細描述每次循環(huán)都將搜索區(qū)間減半，因此需要logn次循環(huán)才能找到目標值或確定目標值不存在。在最壞情況下，即目標值不存在于數(shù)組中，二分搜索的時間復雜度仍為O(logn)。二分搜索的時間復雜度04黃金分割搜索黃金分割搜索的定義黃金分割搜索是一種一維搜索算法，它通過將搜索區(qū)間不斷二分來尋找目標值。它利用了黃金分割的思想，即每次將搜索區(qū)間一分為二，然后根據(jù)目標值所在的區(qū)間進行下一次搜索。重復重復步驟2和3，直到找到目標值或搜索區(qū)間長度小于某個預設的閾值。初始化設置初始搜索區(qū)間為整個數(shù)據(jù)范圍，并設置初始步長為數(shù)據(jù)范圍的1/4。二分搜索將搜索區(qū)間不斷二分，每次取區(qū)間的中點作為猜測值。判斷如果猜測值等于目標值，則搜索結束；否則，根據(jù)目標值與猜測值的比較結果，將非目標值的區(qū)間縮短一半，并繼續(xù)進行下一輪二分搜索。黃金分割搜索的步驟黃金分割搜索的時間復雜度為O(logn)，其中n為數(shù)據(jù)范圍。因為每次都將搜索區(qū)間長度減半，所以需要進行多次二分搜索才能找到目標值。與線性搜索和二分搜索相比，黃金分割搜索在數(shù)據(jù)范圍較大時具有更高的效率。黃金分割搜索的時間復雜度05拋物線搜索拋物線搜索是一種一維搜索算法，用于在有序數(shù)組中查找特定元素。它通過比較目標值與數(shù)組中間元素的差值，決定下一步搜索的方向，從而縮小搜索范圍。拋物線搜索基于二分搜索的思想，但不受二分搜索的限制，可以在任意位置開始搜索。拋物線搜索的定義拋物線搜索的步驟0102032.計算當前區(qū)間的中間元素。3.比較中間元素與目標值1.初始化當前搜索區(qū)間為整個數(shù)組。02030401拋物線搜索的步驟如果中間元素等于目標值，返回該位置。如果目標值小于中間元素，將左半部分區(qū)間作為新的當前區(qū)間。如果目標值大于中間元素，將右半部分區(qū)間作為新的當前區(qū)間。4.重復步驟2和3，直到找到目標值或當前區(qū)間為空。最壞情況下，拋物線搜索的時間復