萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 資料結構與演算法:搜尋演算法 (循序/二分) 完整實作

前言

搜尋是程式設計最基礎的操作。本文實作「循序搜尋」與「二分搜尋」,並延伸「尋找最大/最小值」、「計算重複次數」,附完整代碼與複雜度分析。

一、循序搜尋 - Sequential Search

適用於**未排序**資料,從頭掃描至尾。

基本版:回傳布林值

function seqSearch(data, arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === data) return true;
  }
  return false;
}

進階版:回傳索引位置

function seqSearchIndex(data, arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === data) return i;
  }
  return -1;
}

時間複雜度:O(n) | 空間複雜度:O(1)

二、尋找最大值與最小值

最小值

function findMin(arr) {
  if (!arr.length) return undefined;
  let min = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
  }
  return min;
}

最大值

function findMax(arr) {
  if (!arr.length) return undefined;
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

單趟掃描同時找最大最小可減少比較次數 (每兩個元素 3 次比較)。

三、二分搜尋 - Binary Search

前提:陣列必須已排序 (升序)。

核心邏輯

function binSearch(data, arr) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] < data) low = mid + 1;
    else if (arr[mid] > data) high = mid - 1;
    else return mid; // 找到
  }
  return -1; // 不存在
}

複雜度分析

  • 時間:O(log n) - 每次排除一半資料。
  • 空間:O(1) - 僅用常數變數。

完整測試 (含快速排序前置)

// 快速排序 (輔助測試)
function qSort(list) {
  if (list.length === 0) return [];
  const pivot = list[0];
  const left = [], right = [];
  for (let i = 1; i < list.length; i++) {
    list[i] < pivot ? left.push(list[i]) : right.push(list[i]);
  }
  return [...qSort(left), pivot, ...qSort(right)];
}

const numbers = [0,9,1,8,7,6,2,3,5,4];
const sorted = qSort(numbers); // [0,1,2,3,4,5,6,7,8,9]
console.log(binSearch(6, sorted)); // 6 (索引)

四、計算重複次數 (二分搜尋延伸)

二分搜尋找到目標後,向左右擴展計算相同值數量。

function countOccurrences(data, arr) {
  const pos = binSearch(data, arr);
  if (pos === -1) return { count: 0, indexes: [] };

  let count = 1;
  const indexes = [pos];

  // 向左掃描
  for (let i = pos - 1; i >= 0 && arr[i] === data; i--) {
    count++; indexes.unshift(i);
  }
  // 向右掃描
  for (let i = pos + 1; i < arr.length && arr[i] === data; i++) {
    count++; indexes.push(i);
  }
  return { count, indexes };
}

const arr = [0,1,1,1,2,3,4,5,6,7,8,9];
console.log(countOccurrences(1, arr)); // { count: 3, indexes: [1,2,3] }

效能比較總結

演算法前提條件時間複雜度適用場景
循序搜尋無序O(n)小資料量、未排序、單次查詢
二分搜尋已排序 (升序)O(log n)大資料量、頻繁查詢、靜態資料
雜湊表 (Map/Object)無序O(1) 平均極高頻查詢、鍵值對存取

進階補充

  • 內建方法:arr.indexOf() (循序)、arr.find()、arr.findIndex()。
  • 下界/上界:lower_bound (第一個 >= target)、upper_bound (第一個 > target) 可用二分變體實作,適用區間查詢。
  • 插值搜尋:資料均勻分布時優於二分,O(log log n)。

總結

理解搜尋演算法的前提條件與複雜度權衡是工程師基本功。實務上:小資料用 indexOf/includes,大量靜態排序資料用二分 (或 Array.prototype.binarySearch Polyfill),高頻動態查詢用 Map/Set。

copyright © 萬盛學電腦網 all rights reserved