Revisions to Sentinel linear search

added 74 characters in body

Source Link

edited Sep 1, 2020 at 6:51

8.6k
1
13
26

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 for a , 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.

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 for a , it would make more sense to use the built-in indexOf method, which would be far faster and easier.

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.

added 998 characters in body

Source Link

edited Sep 1, 2020 at 5:06

CertainPerformance

8.6k
1
13
26

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 for a , it would make more sense to use the built-in indexOf method, which would be far faster and easier.

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 for a , it would make more sense to use the built-in indexOf method, which would be far faster and easier.

deleted 4 characters in body

Source Link

edited Sep 1, 2020 at 4:49

CertainPerformance

8.6k
1
13
26

const linearSearchSentinel = (array, itemToFind) => {
    const { length } = array;
    array.push(itemToFind);
    for (let i = 0;; i++) {
        if (array[i] === itemToFind) {
            array.shiftpop(); // 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');

const linearSearchSentinel = (array, itemToFind) => {
    const { length } = array;
    array.push(itemToFind);
    let i = 0;
    while (array[i] !== itemToFind) i++;
    array.shiftpop(); // 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');

const linearSearchSentinel = (array, itemToFind) => {
    const { length } = array;
    array.push(itemToFind);
    for (let i = 0;; i++) {
        if (array[i] === itemToFind) {
            array.shift(); // 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');

const linearSearchSentinel = (array, itemToFind) => {
    const { length } = array;
    array.push(itemToFind);
    let i = 0;
    while (array[i] !== itemToFind) i++;
    array.shift(); // 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');

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');

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');

deleted 102 characters in body

Source Link

edited Aug 31, 2020 at 21:32

CertainPerformance

8.6k
1
13
26

Loading

Source Link

created Aug 31, 2020 at 21:25

CertainPerformance

8.6k
1
13
26

Loading

Stack Exchange Network

Return to Answer