搜尋是程式設計最基礎的操作。本文實作「循序搜尋」與「二分搜尋」,並延伸「尋找最大/最小值」、「計算重複次數」,附完整代碼與複雜度分析。
適用於**未排序**資料,從頭掃描至尾。
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 次比較)。
前提:陣列必須已排序 (升序)。
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; // 不存在
}
// 快速排序 (輔助測試)
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) 可用二分變體實作,適用區間查詢。理解搜尋演算法的前提條件與複雜度權衡是工程師基本功。實務上:小資料用 indexOf/includes,大量靜態排序資料用二分 (或 Array.prototype.binarySearch Polyfill),高頻動態查詢用 Map/Set。