數據結構:數組:線性查找(Linear Search)

目錄

什么是線性查找?

時間復雜度分析

🧠?線性查找的優化

方法一:Move to Front(哨兵)?

方法二:Transportation(向前交換一步)?


什么是線性查找?

我們先問:你想做什么?

你現在有一個數組:

A = [3, 5, 9, 7, 2, 6]

你想查找一個值,比如 7,問:

? 它在數組中的哪個位置?

從前往后,一個一個看!

也就是說:

  • 比較 A[0] 是不是 7?不是

  • 比較 A[1] 是不是 7?不是

  • 比較 A[2] 是不是 7?不是

  • 比較 A[3] 是不是 7?? 是!

找到它的位置啦,返回 3!

這就是——線性查找(Linear Search)?

從數組的 第一個元素開始,一個一個往后找,直到找到目標值,或者整個數組都遍歷完。?

  • 數組 A,長度 n

  • 要查找的目標值 key

查找過程:

  • 遍歷數組中每一個元素

  • 如果某個元素等于 key,返回它的索引

  • 如果一直沒找到,說明它不存在,返回 -1

那么如果沒找到怎么辦?

你需要返回一個“不可能的合法索引”來表示失敗。

?為什么選 -1?

  • 數組索引是從 0 開始的,最小索引是 0

  • 所以 -1 永遠不是合法索引 → 非常適合表示 “查找失敗”

int linearSearch(int A[], int n, int key) {for (int i = 0; i < n; i++) {if (A[i] == key) {return i;  // 找到了,返回位置}}return -1;  // 沒找到
}

時間復雜度分析

情況比較次數時間復雜度
最好情況(第一個就找到)1 次O(1)
最壞情況(最后一個找到或找不到)n 次O(n)
平均情況≈ n/2 次O(n)

結論:🕒 時間復雜度是 O(n)

因為你可能需要檢查數組中每一個元素。?

空間復雜度分析

你只是訪問數組,沒有開新空間 → ? 空間復雜度是:O(1)(常數)

線性查找的適用場景

適合情況不適合情況
?數組無序?數組有序(用二分更快)
?數據量小?數據量大
?查找頻率低?查找頻率高

🧠?線性查找的優化

我們從最根本的問題問起:我們為什么需要優化線性查找??

for (int i = 0; i < n; i++)if (A[i] == key)return i;

原始線性查找算法的時間復雜度是 O(n),也就是說:

  • 如果數組很長,查找一個元素可能非常慢;

  • 每次都要從頭開始;

  • 哪怕你經常查找的是第 98 個元素,也要前面白比對 97 次。

?Step 1:識別性能瓶頸

我們思考:

線性查找性能差的根源是什么?

答:不知道哪些值常用,每次都必須從頭查到尾。

?Step 2:尋找提升策略(性能原理)

我們繼續問:

有什么辦法能讓「經常被查找的值」查得更快?

思路:

  • 如果某些值經常被查找,我們能不能讓它們靠前一點?

  • 這樣,下次查找時更容易「提前命中」

這就是“利用訪問頻率的非均勻性(局部性)” —— 稀疏的優化策略

? Step 3:能不能改變數組順序?

思考:

原來的數組是按什么順序排的?

線性查找不要求有序 → ?我們可以調整順序!

也就是說,我們可以「根據使用情況」來調整數組布局,讓常查元素靠前

? Step 4:目標明確:讓“熱點元素”靠前

現在我們有了優化目標:

每次找到目標之后,想辦法把它往前移!

這樣下次更容易早找到。

?? Step 5:兩種“往前移”的方式自然浮現

方法一:Move to Front(哨兵)?

📌 思考方式:

既然你這么重要,我就把你提到最前面,以后第一個找你!

操作步驟:

  1. 找到元素 A[i]

  2. 將其值保存為 temp

  3. 從 i 往前,把 A[j-1] 移動到 A[j]

  4. 把 temp 放在 A[0]

為什么合理?

  • 查過一次,就代表可能未來還會查 → 越早命中越好

  • 不考慮“穩定性”,直接調整順序 → 速度最優

原地移動(圖示)

原數組:

[3][5][9][7][2]    ← 要查找 7↑

找到 A[3] == 7
→ 把 7 放到 A[0]
→ 其他人向后退一格:

結果:

[7][3][5][9][2]

優化后平均查找時間會降低,因為如果 7 是高頻元素,那么:

  • 查找第一次:代價 O(n)

  • 查找第二次:它已經在最前面了!→ O(1)


方法二:Transportation(向前交換一步)?

📌 思考方式:

如果你被查到了,我讓你「進一格」,但不會一下子到最前

操作步驟:

  1. 找到元素 A[i]

  2. 與 A[i?1] 交換

為什么要這么溫和?

  • 如果一查就放最前,有可能誤判“偶然熱點”

  • Transpose 是「緩慢上升」→ 更公平,更“穩定”

原地交換(圖示)

原數組:

[3][5][9][7][2]↑

找到 A[3] = 7
→ 與 A[2] = 9 交換

結果:

[3][5][7][9][2]

?下次再查到,就會再往前。


? Step 6:代碼實現

Move to Front:

int linearSearchMoveToFront(int A[], int n, int key) {for (int i = 0; i < n; i++) {if (A[i] == key) {// 將 A[i] 移動到前面int temp = A[i];for (int j = i; j > 0; j--) {A[j] = A[j - 1];}A[0] = temp;return 0;  // 返回新位置}}return -1;
}

Transportation:?

int linearSearchTranspose(int A[], int n, int key) {for (int i = 0; i < n; i++) {if (A[i] == key) {if (i > 0) {swap(A[i], A[i - 1]);return i - 1;}return i;}}return -1;
}

這就是從“行為本質”出發的兩種優化策略!

總結:

從第一性原理出發,線性查找的本質缺陷是“對所有元素一視同仁”。

而優化的核心思想是:

“把重要的人提前排隊”,不讓高頻元素總排在后面白等。

Move-to-front 是“VIP 通道”,Transpose 是“按表現升位”。?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/88046.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/88046.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/88046.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

石子入水波紋效果:UV擾動著色器實現

利用UV坐標擾動來模擬水面是一種常見且有效的技術手段,上述效果主要通過對水面紋理的UV坐標進行動態偏移或擾動,從而模擬水波的流動和波紋效果。資源下載具體實現和原理如下: 基本思路:通過對水面紋理的UV坐標加上時間相關的擾動函數(如正弦波、余弦波、噪聲函數等),使紋…

Java Lambda 類型推斷詳解:filter() 方法與 Predicate<? super T>

一、問題核心解析1. 代碼示例分析List<String> strings Arrays.asList("abc", "", "bc", "efg", "abcd","", "jkl"); List<String> filtered strings.stream().filter(string -> !str…

XSS:xss.haozi.me靶場練習

超鏈接:alert(1) 知識點: html <&#xff01;--被注釋的內容--> <&#xff01;--被注釋的內容!--> php /*被注釋的內容*/ //被注釋的內容 javascript /*被注釋的內容*/ //被注釋的內容 MySQL …

ubuntu 20.04 安裝中文輸入法 (sougou pin yin)

安裝搜狗輸入法包 參照官方指南完成 如果提示沒有找到相關依賴&#xff0c;添加一下源&#xff1a; sudo add-apt-repository universe sudo apt update重啟。

(DETR)End-to-End Object Detection with Transformers論文精讀(逐段解析)

(DETR)End-to-End Object Detection with Transformers論文精讀&#xff08;逐段解析&#xff09; 論文地址&#xff1a;https://arxiv.org/abs/2005.12872 CVPR 2020 Facebook AI 發布 Abstract. We present a new method that views object detection as a direct set pred…

[linux][shell]通過分析 Nginx 的訪問日志,檢測異常 IP 地址并使用iptables 將其封禁

這段腳本的作用是通過分析 Nginx 的訪問日志&#xff0c;檢測異常的 IP 地址&#xff0c;并使用 iptables 封禁這些 IP。#!/bin/bash# 配置變量 LOG_FILE"/usr/local/nginx/logs/access.log" THRESHOLD10 DROP_LOG_FILE"/tmp/drop_ip.log" DATE$(date &quo…

stm32cube ide如何將工具鏈替換成arm-none-eabi-gcc

在 STM32Cube IDE 中替換工具鏈為GNU Arm Embedded Toolchain (arm-none-eabi-gcc)&#xff0c;可按以下步驟操作&#xff1a; 1. 檢查是否已安裝工具鏈 首先確認系統中是否已安裝 arm-none-eabi-gcc&#xff1a; Windows&#xff1a;檢查環境變量 PATH 中是否包含工具鏈路徑…

Linux 系統 /etc/ 配置

在Linux系統中&#xff0c;/etc/ 目錄是系統配置文件的核心存放位置&#xff0c;包含了各種系統服務、應用程序和硬件的配置信息。以下是該目錄下常見的重要配置文件和子目錄&#xff1a; 核心系統配置文件 /etc/hostname 系統主機名配置&#xff0c;直接決定當前系統的名稱。/…

【跟著PMP學習項目管理】項目管理 之 成本管理知識點

目錄 一、估算成本 1、知識點匯總 2、輸入 3、工具 4、輸出 二、預算成本 1、知識點匯總 2、輸入 3、工具 4、輸出 三、控制成本 1、知識點匯總 2、輸入 3、工具 4、輸出 一、估算成本 1、知識點匯總 1) 估算工具的用法 2、輸入 范圍基準、人力資源計劃、項…

TCP相關實驗

目錄 TCP相關實驗 理解CLOSE_WAIT狀態 理解???TIME_WAIT狀態 解決TIME_WAIT狀態引起的bind失敗的方法 理解listen的第二個參數 ?編輯 使用Wireshark分析TCP通信流程 TCP與UDP TCP與UDP對比 用UDP實現可靠傳輸&#xff08;經典面試題&#xff09; TCP相關實驗 理解…

Spring Boot項目初始化:官方與阿里云服務地址對比指南

服務提供商 官方&#xff08;start.spring.io Spring&#xff09; 官方提供的服務&#xff0c;由Pivotal&#xff08;VMware&#xff09;維護&#xff0c;是標準的初始化工具。 阿里云&#xff08;start.aliyun.com&#xff09; 阿里云提供的國內鏡像服務&#xff0c;針對中國開…

創客匠人創始人IP案例:從個人品牌到企業增長的全鏈路拆解

認知破局&#xff1a;為什么創客匠人創始人IP能撬動企業增長&#xff1f;在知識付費工具競爭同質化的當下&#xff0c;創客匠人創始人老蔣以“IP變現領軍人”的IP形象&#xff0c;為企業打開了差異化增長通道。當同行還在比拼“功能數量”時&#xff0c;老蔣通過《領導者請停止…

UVC(USB Video Class,USB 視頻類)協議

UVC&#xff08;USB Video Class&#xff0c;USB 視頻類&#xff09;協議并非專門僅用于相機&#xff0c;但其核心應用場景集中在視頻采集設備&#xff0c;相機是最典型的代表。其適用設備除了常見的 USB 相機&#xff08;包括 webcam、工業相機、監控攝像頭等&#xff09;&…

如何使用 eBPF 監控 Linux 內存情況:Linux 內存調優之 eBPF 內存監控分析

寫在前面 博文內容整理自 《BPF Performance Tools》 書中 內存部分對書中提到BPF工具配合實際Demo進行說明,以及一些變體的輸出涉及下面一些內存問題的 BPF 觀測 Demo:為什么進程的物理內存占用(RSS)不停增長?哪些代碼路徑會導致缺頁錯誤的發生,缺頁錯誤來自哪些文件?大頁的…

SQL 表結構轉 Go、Java、TS 自定義實體類,支持自編模板

SQL 表結構一鍵轉自定義模型&#xff0c;支持 Golang Template 自由編寫&#xff01; 有沒有想過 —— 一份 SQL 表結構&#xff0c;不止能轉成 Java 實體類、Go struct&#xff0c;甚至可以&#xff1a; ? 一鍵生成 TypeScript 接口? 輸出 Protobuf 定義文件? 輸出任意你…

新型BERT勒索軟件肆虐:多線程攻擊同時針對Windows、Linux及ESXi系統

趨勢科技安全分析師發現&#xff0c;一個代號為BERT&#xff08;內部追蹤名Water Pombero&#xff09;的新型勒索軟件組織正在亞洲、歐洲和美國展開多線程攻擊。該組織主要針對醫療保健、科技和會展服務行業&#xff0c;其活動范圍顯示其正成為勒索軟件生態中的新興威脅力量。攻…

Three.js搭建小米SU7三維汽車實戰(1)搭建開發環境

1.基本概念 ![](https://i-blog.csdnimg.cn/img_convert/a4676122e207e058f3a335df2c99d4f8.png)1) 場景 如何理解場景 場景就是一個三維的世界, 在這個世界中可以放置各種各樣的物體 可以理解成一個**空間**, 或者**容器** 2) 相機 如何理解相機 &#x1f914;**思考: *…

Selenium 原理【selenium】

Selenium 是什么&#xff1f;Selenium 是一個專門用于自動化操作網頁的工具集&#xff0c;它能夠模擬人類在瀏覽器中進行的各種操作&#xff0c;如點擊按鈕、填寫表單、滾動頁面等。借助 Selenium&#xff0c;開發者可以編寫腳本來控制瀏覽器&#xff0c;實現自動化測試、數據采…

【音視頻】HLS-m3u8協議介紹

參考文檔&#xff1a;https://datatracker.ietf.org/doc/html/rfc8216 一、m3u8協議概述 m3u8 協議是基于 M3U 格式擴展而來的一種多媒體播放列表協議&#xff0c;主要用于流媒體的索引和分發&#xff0c;尤其在 HLS&#xff08;HTTP Live Streaming&#xff09;技術中扮演核…

unity入門:動畫等不顯示問題——畫布設置

unity入門&#xff1a;動畫等不顯示問題——畫布設置動畫等不顯示問題大部分原因畫布Canvas總結動畫等不顯示問題大部分原因 1、畫布設置渲染模式不對&#xff0c;下文再講這個問題。 2、在層級雙擊動畫查看動畫大小&#xff0c;有些動畫創建完之后在場景大小實際很小需要在R…