查找是最基礎的算法之一。實踐中主要有兩種方式:順序查找適用於元素隨機排列的列表;二分查找適用於已排序列表,效率更高,但代價是必須先完成排序,且插入刪除成本高。
從列表第一個元素開始逐個比較,直到找到目標或遍歷到末尾。
function seqSearch(data, arr) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return true;
}
}
return false;
}
實務中更有用的是返回位置的版本:
function seqSearch(data, arr) {
for (var i = 0; i < arr.length; ++i) {
if (arr[i] == data) {
return i;
}
}
return -1;
}
思路一致:先把首元素當作當前最值,然後遍歷其餘元素逐一比較,遇到更合適的就更新。
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;
}
算法步驟:
Math.floor((上界 + 下界) / 2)。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;
}
配合快速排序使用(這裡用最直觀的分區寫法便于理解):
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)); // 6
二分查找找到某個值後,只保證停在「其中一個」匹配位置上。如果數據集中還有其他相同值,它們可能分布在該位置的左側或右側。因此需要用兩個循環向兩邊掃描:
function count(data, arr) {
var count = 0;
var arrs = [];
var position = binSearch(data, arr);
if (position > -1) {
++count;
arrs.push({ "index": count });
// 向左掃描
for (var i = position - 1; i >= 0; --i) {
if (arr[i] == data) {
++count;
arrs.push({ "index": count });
} else {
break; // 遇到不同的值立即停止
}
}
// 向右掃描
for (var j = position + 1; j < arr.length; ++j) {
if (arr[j] == data) {
++count;
arrs.push({ "index": count });
} else {
break;
}
}
}
return arrs;
}
var arr = [0, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var arrs = count(1, arr);
console.log(arrs);
console.log(arrs.length);

由於有序數組中相同元素必然相鄰,掃描時一旦遇到不同的值就可以 break,不必遍歷全表。這是「有序」這個前提帶來的額外紅利。
如果要求更高性能(比如統計百萬級數據中的中位數或眾數),可以改寫二分查找使其返回「第一個等於目標的位置」和「最後一個等於目標的位置」,兩者下標之差加一即為出現次數,時間複雜度可壓到 O(log n)。