在數據結構中搜索：解釋不同的搜索方法
已發表: 2021-05-03通訊網絡在擴大，人們也在使用互聯網！ 企業正在走向數字化以實現高效管理。 互聯網上生成的數據正在增加，因此數據集變得越來越複雜。 仔細而有效地組織、管理、訪問和分析數據是必不可少的，數據結構是最有用的技術，本文重點關注這一點！
目錄
數據結構
在計算機科學中，數據結構是抽像數據類型 (ADT) 的基礎，其中 ADT 是數據類型的邏輯形式。 數據類型的物理佈局是使用數據結構實現的。 不同的數據結構類型用於不同類型的應用程序； 有些專門從事特定任務。
數據結構是數據值和它們之間的關係、適用於數據的操作和功能的集合。 它有助於以特定格式組織、管理和存儲數據。 因此，用戶可以輕鬆訪問和有效地修改數據。
數據結構有助於管理大量數據，例如海量數據庫。 高效的算法是建立在高效的數據結構之上的。 除了有效的存儲之外，數據結構還負責從存儲的內存中有效地檢索信息。 它包括數組、鍊錶、指針、搜索、堆棧、圖形、隊列、結構、程序、排序等。
本文介紹了在數據結構中搜索的概念及其方法。 詳細解釋了兩個算法示例，以清楚地理解概念。 為了獲得更多的知識、技能和專業知識，可以使用文章末尾提到的數據結構在線課程。
什麼是數據結構中的搜索？
從以元素形式存儲在計算機內存中的一組項目中查找所需信息的過程稱為“在數據結構中搜索”。 這些項目集有多種形式，例如數組、樹、圖形或鍊錶。 在數據結構中定義搜索的另一種方法是在項目集合中定位特定特徵的所需元素。
搜索方法
數據結構中的搜索可以通過實現搜索算法來從任何形式的存儲數據結構中檢查或檢索元素來完成。 這些算法根據其搜索操作的類型進行分類，例如：
- 順序搜索
在檢查集合的每個組件時，依次遍歷數組或元素列表。
例如，線性搜索。
- 區間搜索
明確設計用於在排序數據結構中搜索的算法包含在區間搜索中。 這些算法的效率遠遠優於線性搜索算法。
例如，二分搜索、對數搜索。
這些方法是根據算法搜索與數據集合中的搜索項匹配的元素所花費的時間進行檢查的，由下式給出，
- 最好的時間
- 平均時間
- 最壞情況時間
主要關注的是最壞情況時間，這會導致對算法性能的有保證的預測，並且與平均時間相比也很容易計算。
為了說明本文中的示例和概念，我們考慮了任何數據格式的數據集合中的“n”個項目。 顯性操作用於簡化分析和算法比較。 對於數據結構中的搜索，比較是一種主要操作，用 O() 表示，發音為“big-Oh”或“Oh”。
數據結構中有許多搜索算法，例如線性搜索、二進制搜索、插值搜索、跳轉搜索、指數搜索、斐波那契搜索、子列表搜索、無處不在的二進制搜索、無界二進制搜索、子字符串搜索的遞歸函數和遞歸程序在給定數組中線性搜索元素。 本文僅限於線性和二進制搜索算法及其工作原理。
讓我們詳細了解數據結構中的線性搜索和二分搜索。
線性搜索
線性搜索算法按順序搜索數組中的所有元素。 它的最佳執行時間是 1，而最差執行時間是 n，其中 n 是搜索數組中的項目總數。
它是數據結構中最簡單的搜索算法，檢查元素集合中的每一項，直到它與搜索元素匹配，直到數據收集結束。 當數據未排序時，首選線性搜索算法。
線性搜索有一些複雜性，如下所示：
- 空間複雜度
線性搜索的空間複雜度為 O(n)，因為它不使用任何額外空間，其中 n 是數組中元素的數量。
- 時間複雜度
*當搜索元素出現在搜索數組中的第一個元素時，最佳情況復雜度 = O(1)。
*當搜索元素不存在於元素集或數組中時，最壞情況復雜度 = O(n)。
*當元素出現在搜索數組中的某處時，指的是平均複雜度 = O(n)。
例子，
讓我們採用如下所示的元素數組：
45、78、12、67、08、51、39、26
為了在上面給出的 8 個元素的數組中找到“51”，線性搜索算法將依次檢查每個元素，直到其指針指向內存空間中的 51。 在數組中找到 51 需要 O(6) 時間。 要找到 12，在上面的數組中，它需要 O(3)，而對於 26，它需要 O(8) 時間。
二進制搜索
該算法通過比較數據集合中最中間的項目來查找特定項目。 當匹配發生時，它返回項目的索引。 當中間項大於該項時，它會搜索左子數組的中心項。 相反，如果中間項小於搜索項，則在右子數組中探索中間項。 它繼續搜索一個項目，直到找到它或直到子數組大小變為零。
二分搜索需要對項目進行排序。 它比線性搜索算法快。 它的工作原理是分而治之。
運行時復雜度 = O(log n)
二分查找算法的複雜性如下：
- 最壞情況復雜度 = O (n log n)
- 平均複雜度 = O (n log n)
- 最佳情況復雜度 = O (1)
例子，
讓我們採用 08 個元素的排序算法：
08、12、26、39、45、51、67、78
要在上述元素的數組中找到 51，
該算法會將一個數組分成兩個數組，08、12、26、39和45、51、67、78
由於 51 大於 39，它將開始搜索數組右側的元素。
它將進一步分為兩個，例如 45、51 和 67、78
由於 51 小於 67，它將開始搜索該子數組的左側。
該子數組再次分為兩部分，分別為 45 和 51。
由於 51 是與搜索元素匹配的數字，因此它將返回其在數組中該元素的索引號。
它將得出結論，搜索元素51位於數組中的第6個位置。
由於比較計數比線性搜索算法顯著減少，二分搜索將時間減少到一半。
閱讀： Python 中的數據結構類型
插值搜索
它是二分搜索算法的改進變體，適用於搜索元素的探測位置。 與二分搜索算法類似，它僅在排序的數據集合上有效。
最差執行時間 = O(n)
當目標元素的位置在數據集合中已知時，將使用插值搜索。 要在電話簿中查找一個號碼，如果要搜索莫妮卡的電話號碼，可以直接探查名字以“M”開頭的內存空間存儲，而不是使用線性或二分法搜索。
結論
在數據結構中搜索是指在“n”個元素的數組中找到給定的元素。 有兩類，即。 搜索中的順序搜索和區間搜索。 幾乎所有的搜索算法都基於這兩個類別之一。 線性和二進制搜索是兩種簡單且易於實現的算法，其中二進制比線性算法工作得更快。
雖然線性搜索最直接，但它會檢查每個元素，直到找到與搜索元素匹配的內容，因此在數據收集未正確排序時非常有效。 但是，如果數據集合是有序的並且數組的長度相當大，那麼二進制搜索會更快。
在處理數據集時，數據結構是計算機編程的重要組成部分。 程序員和開發人員需要通過計算機編程技術的基礎知識和更新不斷更新和提升自己的技能。 處理數據結構的程序員應該經常選擇課程。
如果您想了解有關數據科學的更多信息，請查看 IIIT-B 和 upGrad 的數據科學執行 PG 計劃，該計劃是為在職專業人士創建的，並提供 10 多個案例研究和項目、實用的實踐研討會、與行業專家的指導，與行業導師一對一，400 多個小時的學習和頂級公司的工作協助。
