查找資料基本上有兩條路:順序搜尋與二分搜尋。順序搜尋適用於任意排列的資料,實作單純;二分搜尋效率高得多,但前提是資料必須已排序。本文把這兩者與相關的極值查找、重複值計數一起整理。
從第一個元素開始逐個比對,直到找到或走完整個清單。
// 回傳布林值
function seqSearch(data, arr) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return true;
}
}
return false;
}
// 回傳位置,找不到則回 -1(實務上更有用)
function seqSearch(data, arr) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return i;
}
}
return -1;
}
時間複雜度 O(n),平均需比較 n/2 次。
演算法步驟(以最小值為例):
1. 把第一個元素設為目前最小值。
2. 從第二個元素開始依序與目前最小值比較。
3. 若當前元素更小,就把它設為新的最小值。
4. 前進到下一個元素,重複步驟 3。
5. 走訪結束時,變數中存的就是最小值。
function findMin(arr) {
var min = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
function findMax(arr) {
var max = arr[0];
for (var i = 1; i < arr.length; ++i) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
兩者都是 O(n)。實務上 Math.min(...arr) 更簡潔,但資料量龐大時有參數上限問題,此時用 reduce 一次同時取極值會更好。
演算法步驟:
1. 下邊界定為 0,上邊界定為 length − 1。
2. 當下邊界 <= 上邊界時:
A. 中點 = (上邊界 + 下邊界) / 2 取整數。
B. 中點值 < 目標 → 下邊界 = 中點 + 1。
C. 中點值 > 目標 → 上邊界 = 中點 − 1。
D. 相等 → 找到,回傳位置。
3. 迴圈結束仍未回傳,代表不存在,回傳 -1。
function binSearch(data, arr) {
var lowerBound = 0;
var upperBound = arr.length - 1;
while (lowerBound <= upperBound) {
var mid = Math.floor((upperBound + lowerBound) / 2);
if (arr[mid] < data) {
lowerBound = mid + 1;
} else if (arr[mid] > data) {
upperBound = mid - 1;
} else {
return mid;
}
}
return -1;
}
時間複雜度 O(log n),這是它與順序搜尋最關鍵的差異。
二分搜尋要求輸入有序,所以實用上通常先排序。以下用快速排序把整組流程串起來:
function qSort(list) {
if (list.length == 0) return [];
var left = []; // 小於基準值
var right = []; // 大於或等於基準值
var pivot = list[0];
for (var i = 1; i < list.length; i++) {
if (list[i] < pivot) {
left.push(list[i]);
} else {
right.push(list[i]);
}
}
return qSort(left).concat(pivot, qSort(right));
}
var numbers = [0, 9, 1, 8, 7, 6, 2, 3, 5, 4];
var list = qSort(numbers);
console.log(binSearch(6, list)); // 5
binSearch 找到目標時,只保證停在「某一個」符合的位置,其他相同值可能落在它左側或右側。最直覺的做法是從該位置向兩邊各走一趟,連續相同就計數:
function count(data, arr) {
var count = 0;
var positions = [];
var position = binSearch(data, arr);
if (position > -1) {
++count;
positions.push(position);
// 向左掃
for (var i = position - 1; i >= 0; --i) {
if (arr[i] == data) {
++count;
positions.push(i);
} else {
break;
}
}
// 向右掃
for (var j = position + 1; j < arr.length; ++j) {
if (arr[j] == data) {
++count;
positions.push(j);
} else {
break;
}
}
}
return { count: count, positions: positions };
}
var arr = [0, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(count(1, arr));
執行結果如下圖:

重複值多的情況可用「找邊界」。上面向兩側掃描在「全部元素都相同」時會退化為 O(n)。更穩健的做法是寫 lowerBound 與 upperBound 兩個變體二分搜尋,各自找出區間起訖,重複次數就是兩者相減,整體維持 O(log n)。
注意 == 與 === 的差別。本文範例沿用 == 以便說明演算法;實務上請用 ===,避免 "1" 與 1 這類型別混淆造成誤判。