Sentinel linear search

Question

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 {
                return console.log('NOT FOUND');
            }
        }
    }
})();

Answer 1

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('NOT FOUND');
            }
            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) {
        return console.log('NOT FOUND');
    }
    console.log('FOUND ON INDEX', i);
};

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

It's also a good idea to prefer const over let when you don't need to reassign the variable name.

I'd prefer one of the easy-to-understand versions above, but if you really want to avoid changing the length of the array for optimization purposes, I suppose you could replace the last item similar to you're originally doing instead.

const linearSearchSentinel = (array, itemToFind) => {
    const { length } = array;
    const lastItem = array[length - 1];
    array[length - 1] = itemToFind;
    let i = 0;
    while (array[i] !== itemToFind) i++;
    array[length - 1] = lastItem;
    console.log(
        (i !== length - 1 || lastItem === itemToFind)
            ? 'FOUND ON INDEX ' + i
            : 'NOT FOUND'
    );
};

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

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.