配列 arr から要素 x を検索したい時は、以下のようなコードを書きます。非常に簡単で、僕もこれを使います。
function linearSearch(x) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
for (var i = 0; i < arr.length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
同じ線形探索でも、配列の最後尾に番兵を用意すると、カウンタ比較の計算が無い分、早くなります。
function linerSearch(x) {
var i = 0;
arr.push(x);
while (arr[i] != x) {
i++;
}
arr.pop();
if (i < arr.length) {
return i;
} else {
return -1;
}
}
var i = 0;
arr.push(x);
while (arr[i] != x) {
i++;
}
arr.pop();
if (i < arr.length) {
return i;
} else {
return -1;
}
}
50000 件の配列から 49999 番目にある要素を検索した場合、前者だと約 400ms で、後者だと約 280ms でした。若干早いです。