Algo python 作者: Joy Liu

【Python】linear search 線性搜尋｜演算法介紹、新手快速入門

基本概念

線性搜尋（Linear Search），又稱為順序搜尋，是一種基本的搜尋演算法，用於在一個資料集合（通常是一個陣列或串列）中尋找特定元素的位置或值。其基本概念如下：

步驟：  

  1. 從資料集合的第一個元素開始，逐一檢查每個元素，直到找到目標元素或搜索完整個集合。
  2. 對比目前檢查的元素與目標元素是否相等。如果相等，則表示找到了目標元素，並返回其位置（索引）。如果不相等，繼續檢查下一個元素。
  3. 如果搜尋完整個資料集合仍未找到目標元素，則返回一個特定的標記（例如-1），表示目標元素不存在於集合中。

特點：

  • 線性搜尋是一種簡單而直觀的搜尋方法，適用於小型資料集合或未排序的資料。
  • 它不要求資料集合是按任何特定順序排列的，因為它會逐一檢查每個元素。
  • 時間複雜度為O(n)，其中n是資料集合中的元素數量。最壞情況下，需要搜索整個集合。
  • 線性搜尋適用於資料量不大且搜尋操作不需要高
  • 效率的情況。對於大型、排序過的資料集合，其他搜尋演算法如二分搜尋可能更為適合，因為它們可以在較快的時間內找到目標元素。

線性搜尋雖然簡單，但在某些情況下仍然非常有用，尤其是當資料集合較小或搜尋操作不需要高效率時。

實際應用

以下是使用 Python 實際運用線性搜尋的範例。

假設我們有一個包含數字的列表，我們想要找到特定的數字是否存在於列表中，以及它的索引位置（如果存在）。

def linear_search(arr, target):
     for i in range(len(arr)):
         if arr[i] == target:
             return i  # 找到目標，返回索引位置
     return -1  # 目標不存在於列表中，返回-1
 測試
 my_list = [5, 8, 2, 9, 12, 7, 4]
 target_number = 9

 result = linear_search(my_list, target_number)

 if result != -1:
     print(f"目標數字 {target_number} 存在於列表中，索引位置為 {result}")
 else:
     print(f"目標數字 {target_number} 不存在於列表中")

這個範例中，我們定義了一個名為 linear_search 的函數，它接受兩個參數：一個列表 arr 和一個目標數字 target。函數使用 for 迴圈逐一檢查列表中的元素，如果找到目標數字，則返回該數字在列表中的索引位置，否則返回 -1 表示目標數字不存在於列表中。

在測試部分，我們創建了一個列表 my_list 和一個目標數字 target_number，然後調用 linear_search 函數來尋找目標數字。

最後，我們根據返回值判斷目標數字是否存在於列表中，並顯示結果。

以上是簡單的線性搜尋實例，可以根據不同的需求和資料集合來使用這個演算法。如果資料量非常大或需要更高效率的搜尋，則可能需要考慮其他搜尋演算法。

使用案例

線性搜尋是一種基本的搜尋演算法，它可以應用在許多不同的情況下，特別是當你需要在一個數列或列表中尋找特定項目時。以下是一些可能的線性搜尋程式案例應用：

  1. 查找元素： 最常見的用途是在一個數列或列表中查找特定的元素。例如，你可以使用線性搜尋來查找一個整數是否存在於一個整數列表中。
  2. 字串搜索： 線性搜尋也可用於搜索字串中的特定字符或子字串。你可以遍歷字串中的每個字符，以查找所需的字符或字串。
  3. 文件搜索： 在文件或文本文檔中搜索特定的單詞、短語或模式也是一個常見的應用。你可以一行一行地讀取文件並進行搜索。
  4. 應用程式中的數據過濾： 在應用程式中，你可能需要根據特定條件過濾數據，例如過濾一個包含多個對象的列表，只保留符合特定條件的對象。
  5. 用戶界面： 在用戶界面中，你可以使用線性搜尋來查找和選擇元素。例如，當用戶輸入關鍵字時，你可以使用線性搜尋從一個選項列表中找到匹配的選項。
  6. 數據清理： 在數據處理工作中，你可能需要清理數據以去除重複項目或不需要的數據。線性搜尋可以用於檢測和去除這些項目。
  7. 簡單排序： 在排序算法中，線性搜尋可以用來查找最小或最大的元素，然後將其移動到排序的適當位置。
  8. 遊戲開發： 在遊戲中，你可以使用線性搜尋來查找特定的遊戲對象或碰撞檢測，以確定是否有物體相互交互。
  9. 簡單的推薦系統： 在一個包含用戶數據的數據集中，你可以使用線性搜尋來查找與特定用戶喜好相關的項目。

需要注意的是，線性搜尋算法的效率較低，尤其當數據量大時。對於大型數據集，更高效的搜索算法（例如二分搜索、散列表等）可能更為合適。

然而，在某些簡單的應用中，線性搜尋仍然是一個有效的解決方案。

其他演算法快速通道：

  1. 【Python】什麼是演算法？
  2. 【Python】Stack(堆疊) 資料結構實作
  3. 【Python】linear search 線性搜尋
  4. 【Python】binary search 二分搜尋
  5. 【Python】Single Linked List(單向鏈結串列) 資料結構實作
  6. 【Python】Binary Search Tree (二元搜尋樹) 資料結構實作(1)
  7. 【Python】Binary Search Tree (二元搜尋樹) 資料結構實作(2)

線上學習平台推薦

udemy

我自己最愛用的學習平台是 udemy ，當初會選擇在 udemy 上學習的原因除了課程便宜（當初買的很多課程都300塊左右，是台幣喔台幣！）。

上課時間也可以自己控制（對自律的人來說是一大好處！）

雖然可能有些人會覺得，Youtube上不也很多Tutorials嗎？性質應該差不多吧？而且免費。

雖然看Youtube上也有教學影片，但其實你會發現，這些老師都有另外開課程。

原因也很簡單，只要我們付費購買了他的課程，他就能提供更多的資源來輔助學習，且更有組織的教學過程，甚至有被公司認可的證書。

這就是在免費的youtube上沒辦法做到的。

想知道更多的話，歡迎到【2023】10個使用線上平台學習的好處｜學生、工程師、各行各業皆適用 看完整介紹。

點擊加入Udemy

推薦入門書籍

精通 Python：運用簡單的套件進行現代運算（第二版）

博客來-精通Python：運用簡單的套件進行現代運算（第二版）

之前開始入坑python時就是用這本打底的（有換封面過）

這本書除了前幾張介紹基本的語法之外

後續幾張開始介紹與python相關的延伸性的功能

非常適合程式設計初學者以及剛要開始學習這個語言的讀者

羅列以下幾點關於本書大綱供大家參考

  • 學習簡單的資料類型、基本數學運算與文字操作 
  • 以Python的內建資料結構處理資料 
  • 探索Python程式碼結構，包括函式的使用
  • 使用模組與套件編寫大型Python程式
  • 深入討論物件、類別與其他物件導向功能
  • 檢視一般檔案、關聯式資料庫與NoSQL的儲存機制 
  • 使用Python建構web用戶端、伺服器、API與服務 
  • 管理系統工作，例如程式、程序與執行緒
  • 瞭解並行處理與網路程式設計的基礎
前往博客來購買 -- 中文版
前往博客來購買 -- 英文版

流暢的 Python：清晰、簡潔、有效的程式設計

博客來-流暢的Python：清晰、簡潔、有效的程式設計

適合已經有Python程式語言基礎的人

這本書更詳細的介紹有關python的用法

讓我們寫的程式可以更加"Pythonic"

建議可以與英文版同時閱讀

以後在查閱stackoverflow文獻的時候能不因語言而產生隔閡

  • Python 資料模型：瞭解特殊方法是讓物件具備一致行為的關鍵
  • 資料結構：充分使用內建的型態，並瞭解 Unicode 時代中，文字 vs. bytes 之間的關係
  • 函式就是物件：見識 Python 函式是一級物件，並瞭解這個事實如何影響熱門的設計模式
  • 物件導向的習慣用法：學習參考、可變性、介面、運算子多載與多重繼承，並建構類別
  • 控制流程：藉由 concurrent.futures 與 asyncio 套件，來充分活用情境管理器、產生器、協同程序與並行
  • 中繼編程：瞭解特性、屬性描述器、類別修飾器與中繼類別的工作原理
前往博客來購買 -- 中文版
前往博客來購買 -- 英文版

演算法圖鑑

直觀理解，從基礎開始學習，全圖像化step by step，讓不懂程式的人也能利用圖形了解各種演算法的特質跟運作．

雖然內容並沒有程式實作

但內容演算法流程圖片非常精美

非常適合用來教學或以圖像的方式了解演算法的運作！

前往博客來購買 — 中文版

Python 自動化的樂趣：搞定重複瑣碎&單調無聊的工作(第二版)

Python 自動化的樂趣｜搞定重複瑣碎& 單調無聊的工作(中文版) (Automate the Boring Stuff with Python: Practical Programming for Total Beginners) | 天瓏網路書店

如果想使用自動化來增強工作流程效率，大推本書

之前這本書只有英文版

在博客來等了1個月還是沒等到

沒想到在2020/08/28 出了中文版

二話不說馬上看看人家都是怎麼用python來完成例行公事的

除了運用Python寫出程式，在幾分鐘內搞定人工手動處理需要花費數小時的工作。

探索Python豐富的模組程式庫來完成某些特定工作

例如從網站上抓取資料、讀取PDF和Word文件，以及自動化執行滑鼠點按和鍵盤輸入的工作。

　‧在一個或多個檔案中搜尋文字
　　‧建立、更新、搬移和重新命名檔案和資料夾
　　‧搜尋網頁和下載網路上的圖文內容
　　‧處理PDF檔的分割與合併，加入浮水印和加上密碼等作業
　　‧傳送Email和簡訊
　　‧填寫線上表單

前往博客來購買 — 中文版
前往博客來購買 — 英文版

在〈【Python】linear search 線性搜尋｜演算法介紹、新手快速入門〉中有 3 則留言

  1. 自動引用通知: 【Python】Bubble Sort 泡沫排序｜演算法介紹、新手快速入門 | 愛喝咖啡 Ｘ 咖啡程式
  2. 自動引用通知: 【Python】Selection Sort 選擇排序｜演算法介紹、新手快速入門 | 愛喝咖啡 Ｘ 咖啡程式
  3. 自動引用通知: 【Python】Insertion Sort 選擇排序｜演算法介紹、新手快速入門 | 愛喝咖啡 Ｘ 咖啡程式

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *