# Sentinel linear search

Posted on

Problem

I’m pretty new to algorithms, and it’s my first attempt to implement sentinel linear search in JS. I’m wondering if it can be improved.

``````const array1 = ['lorem', 'ipsum', 'dolor', 'sit', 'amet', 'consectetur', 'adipiscing', 'elit', 'cras', 'eu', 'metus', 'volutpat', 'sagittis', 'nunc', 'in', 'porta', 'quam'];
let i = 0;
let x = 'elit';
let n = array1.length;
let last = array1[n - 1];
array1[n - 1] = x;

(function () {
while (array1[i] !== x) {
i++;
if (array1[i] === x) {
array1[n - 1] = last;
if (array1[i] === x) {
return console.log('FOUND ON INDEX', i);
} else {
}
}
}
})();
``````

Solution

If the point of the sentinel is to, as the wiki article says:

The basic algorithm above makes two comparisons per iteration: one to check if Li equals T, and the other to check if i still points to a valid index of the list. By adding an extra record Ln to the list (a sentinel value) that equals the target, the second comparison can be eliminated until the end of the search, making the algorithm faster.

Then the approach should be to tack on the value to find onto the end of the array, instead of replacing the last value of the array with the value to find. I guess you can replace the last value, then once a match is found, replace it back, then check it, but that’s unnecessarily convoluted.

Your code has a bug: if the first element of the array is the item to search for, `while (array1[i] !== x) {` will evaluate to `false`, and the IIFE will terminate immediately without logging anything.

That test is superfluous anyway, since inside the loop, the array item will either be found before the end, or at the end – either way, `console.log` will be called.

To add an element to the end of an array in JS, it’s easier to use `push`:

``````array1.push(x);
``````

You might consider using more precise variable names, to make the code more readable. (I’d avoid using single-letter variable names except maybe for `i`, which is pretty universally understood to be an index.)

``````const linearSearchSentinel = (array, itemToFind) => {
const { length } = array;
array.push(itemToFind);
for (let i = 0;; i++) {
if (array[i] === itemToFind) {
array.pop(); // remove the added item from array
if (i === length) {
}
return console.log('FOUND ON INDEX', i);
}
}
};

linearSearchSentinel(['foo', 'bar', 'baz'], 'foo');
linearSearchSentinel(['foo', 'bar', 'baz'], 'baz');
linearSearchSentinel(['foo', 'bar', 'baz'], 'nope');``````

Or, if you wanted to use the `while` approach, then don’t put any testing inside the loop – simply increment the index:

``````const linearSearchSentinel = (array, itemToFind) => {
const { length } = array;
array.push(itemToFind);
let i = 0;
while (array[i] !== itemToFind) i++;
array.pop(); // remove the added item from array
if (i === length) {
It’s also a good idea to prefer `const` over `let` when you don’t need to reassign the variable name.
This is all for informational purposes only, of course – if you were actually facing a practical problem where you needed to find the index of an element in an array in JavaScript, it would make more sense to use the built-in `indexOf` method, which would be far faster and easier. Better not to reinvent the wheel unless an assignment like this one requires it.