在 JavaScript 中，線性查找（Linear Search），也叫順序查找，是一種最簡單、最直接的查找算法。它的基本思想是：從數(shù)組（或列表）的第一個元素開始，逐個檢查每個元素，直到找到目標值或遍歷完整個數(shù)組為止。

特點：

• 時間復雜度：
  • 最好情況：O(1)（第一個元素就是要找的）
  • 最壞情況：O(n)（目標在最后一個位置，或者不存在）
  • 平均情況：O(n)
• 空間復雜度：O(1)（不需要額外空間）
• 不要求數(shù)組有序，適用于任何類型的數(shù)組

示例代碼（JavaScript）：

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // 返回目標元素的索引
    }
  }
  return -1; // 未找到，返回 -1
}

// 使用示例
const numbers = [10, 25, 3, 47, 15];
console.log(linearSearch(numbers, 3));  // 輸出: 2
console.log(linearSearch(numbers, 100)); // 輸出: -1

適用場景：

• 數(shù)據量較小
• 數(shù)組未排序
• 只需要查找一次（如果多次查找，建議先排序后用二分查找等更高效方法）

總結：

線性查找雖然效率不高，但實現(xiàn)簡單、通用性強，是理解查找算法的基礎。在 JavaScript 中，原生方法如 Array.prototype.indexOf()、Array.prototype.find() 和 Array.prototype.findIndex() 內部本質上也是線性查找。

面試題解

在前端面試中，線性查找（Linear Search） 雖然算法本身簡單，但常作為考察候選人基礎編程能力、數(shù)組操作熟練度以及對時間復雜度理解的入門題。以下是關于 線性查找在前端面試中的常見題型、解法與注意事項 的全面解析。

一、什么是線性查找？

線性查找（也稱順序查找）是從數(shù)組（或列表）的第一個元素開始，逐個比較每個元素是否等于目標值，直到找到目標或遍歷完整個數(shù)組。

• 適用場景：無序數(shù)組、小規(guī)模數(shù)據
• 時間復雜度：
  • 最壞/平均：O(n)
  • 最好：O(1)（第一個元素即為目標）
• 空間復雜度：O(1)

二、前端面試常見題型

1. 基礎實現(xiàn)：查找目標值首次出現(xiàn)的索引

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1; // 未找到
}

? 考點：for 循環(huán)、嚴格相等（===）、邊界處理

2. 查找所有匹配項的索引（處理重復值）

function findAllIndices(arr, target) {
  const indices = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      indices.push(i);
    }
  }
  return indices.length > 0 ? indices : -1;
}

? 考點：數(shù)組方法 push、返回格式設計（可返回空數(shù)組或 -1）

3. 在對象數(shù)組中查找（需比較屬性）

function findUserById(users, id) {
  for (let i = 0; i < users.length; i++) {
    if (users[i].id === id) {
      return i; // 或 return users[i]
    }
  }
  return -1;
}

// 示例
const users = [{ id: 1, name: 'Alice' }, { id: 2, name: 'Bob' }];
console.log(findUserById(users, 2)); // 1

? 考點：對象訪問、實際業(yè)務場景建模

4. 使用高階函數(shù)實現(xiàn)（考察 ES6 熟悉度）

雖然不是“手寫循環(huán)”，但面試官可能問：

“除了 for 循環(huán)，還能怎么實現(xiàn)？”

// 返回索引
const linearSearch = (arr, target) => arr.indexOf(target);

// 或使用 findIndex（更通用，支持回調）
const linearSearch = (arr, target) => arr.findIndex(item => item === target);

// 查找對象
const findUser = (users, id) => users.findIndex(user => user.id === id);

?? 注意：indexOf 和 findIndex 底層仍是線性查找，時間復雜度不變。

三、高頻追問 & 深度問題

Q1：線性查找和二分查找有什么區(qū)別？

• 線性查找：適用于無序數(shù)組，時間復雜度 O(n)
• 二分查找：必須有序，時間復雜度 O(log n)，但需預排序（O(n log n)）

?? 面試技巧：強調“是否有序”是選擇算法的關鍵前提。

Q2：什么時候用線性查找更合適？

• 數(shù)據量小（如 < 100）
• 數(shù)組無序且不值得排序
• 只需查找一次（排序成本高于線性掃描）
• 需要查找多個條件或復雜對象（難以定義“有序”）

Q3：如何優(yōu)化線性查找？

• 提前終止：找到即返回（默認已做）
• 哨兵法（Sentinel）：減少邊界判斷（較少在 JS 中使用）
• 緩存結果：若多次查同一數(shù)據，可考慮 Map 預處理（轉為哈希查找）

// 預處理為 Map（適合多次查詢）
const buildIndex = (arr) => {
  const map = new Map();
  arr.forEach((item, i) => {
    if (!map.has(item)) map.set(item, []);
    map.get(item).push(i);
  });
  return map;
};

const indexMap = buildIndex([2, 5, 1, 8, 5]);
console.log(indexMap.get(5)); // [1, 4]

? 展示工程思維：從“單次查找”到“多次查找”的優(yōu)化思路。

四、典型面試題示例

題目：編寫一個函數(shù)，在一個字符串數(shù)組中查找包含子串 "react" 的第一個元素的索引。

function findReact(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === 'string' && arr[i].includes('react')) {
      return i;
    }
  }
  return -1;
}

? 考察點：類型安全、字符串方法、邊界意識

五、總結（面試回答模板）

“線性查找是最基礎的查找算法，它通過遍歷數(shù)組逐個比較元素來尋找目標。雖然時間復雜度是 O(n)，但在數(shù)據量小或無序的情況下非常實用。在前端開發(fā)中，我們常用 indexOf、findIndex 或手寫循環(huán)來實現(xiàn)。如果需要頻繁查找，我會考慮用 Map 或 Set 構建哈希表來優(yōu)化到 O(1) 平均時間。”

如果你正在準備前端算法面試，建議：

• 能手寫線性查找（含對象數(shù)組）
• 理解其與 indexOf / findIndex 的關系
• 能對比其他查找算法（二分、哈希）
• 能根據場景選擇合適方案

到此這篇關于js中線性查找的使用的文章就介紹到這了,更多相關js 線性查找內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論