資料結構 - 搜尋演算法

Table of content

在上一節中，我們討論了各種排序技術以及它們可以使用的場景。然而，排序背後的主要思想是將資料以有序的方式排列，從而更容易在已排序的資料中搜索任何元素。

搜尋是在大量資料中查詢特定記錄（可以是單個元素或一小塊資料）的過程。資料可以有多種形式：陣列、連結串列、樹、堆和圖等。隨著當今資料量的不斷增加，有多種技術可以執行搜尋操作。

資料結構中的搜尋演算法

可以將各種搜尋技術應用於資料結構以檢索特定資料。只有當搜尋操作返回所需的元素或資料時，才認為搜尋操作成功；否則，搜尋方法不成功。

這些搜尋技術分為兩類：

顧名思義，順序搜尋操作會順序遍歷每個資料元素以查詢所需資料。此型別的搜尋不需要資料以排序方式排列。

示例 - 線性搜尋

圖1：線性搜尋操作

與順序搜尋不同，區間搜尋操作要求資料以排序方式排列。此方法通常以區間方式搜尋資料；可以透過將資料分成多個子部分或跳過索引來搜尋元素。

示例 - 二分搜尋、跳躍搜尋等。

圖2：二分搜尋操作

通常，並非所有搜尋技術都適用於所有型別的資料結構。在某些情況下，順序搜尋更可取，而在其他情況下，區間搜尋更可取。這些搜尋技術的評估是透過檢查每種搜尋方法在特定輸入上的執行時間來完成的。

這就是漸近符號出現的地方。要了解有關漸近符號的更多資訊，請點選此處。

簡單來說，程式執行的時間複雜度有三種不同的情況：

我們主要關注最佳情況和最壞情況的時間複雜度，因為平均情況難以計算。並且由於執行時間基於提供給程式的輸入量，因此最壞情況時間複雜度最能描述任何演算法的效能。

例如，線性搜尋的最佳情況時間複雜度為O(1)，其中在第一次迭代中找到所需元素；而最壞情況時間複雜度為O(n)，當程式遍歷所有元素但仍然找不到元素時。這被標記為不成功的搜尋。因此，線性搜尋的實際時間複雜度被視為O(n)，其中n是輸入資料結構中存在的元素數量。

許多型別的搜尋方法用於在各種資料結構中搜索資料條目。其中一些包括：

我們將在接下來的章節中詳細介紹每種搜尋方法。

列印頁面