4
\$\begingroup\$

Recently, I've been experimenting with an array searching algorithm that I'm not sure I've seen anywhere (minor references here).

I'm still not fully-learned on how to state the efficiency of what I've done (as per writing it's speed in mathematical notation (e.g.: \$O(\log n)\$) either but I'd like to pass on that this method is most efficient when searching through large non-sorted arrays.

With the tests I've done in JavaScript (which I mainly use to program), it is faster than:

  • Linear searching when the element is at the end of the array.
  • Reversed linear searching when the element is at the start of the array.

This was the original code (but ported to C++):

/* Assert if an element is within an (int) array */
bool includes(int array[], int element, int length) {
    if (length == 1)
        return array[0] == element;

    else if (length) {
        int iterator = length,
            halfLength = (length / 2) >> 0, // Convert to integer.
            quarterLength = (halfLength / 2) >> 0,
            thirdQuarterLength = halfLength + quarterLength;

        // Do not iterate completely through the array
        while (iterator != thirdQuarterLength) {
            iterator -= 1;

            // Check four indexes at once.
            if (
                array[length - iterator - 1] == element ||
                (iterator - halfLength > -1 && array[iterator - halfLength] == element) ||
                (halfLength + (length - iterator - 1) < length) && (array[halfLength + (length - iterator - 1)] == element) ||
                array[iterator] == element
            ) return true;
        }

        return false;
    }

    else
        return false;
}

With this code:

  • The iteration count of the loop is reduced four-fold.
  • Four indexes of the array are queried each iteration of the loop (instead of 1 at a time).
  • The algorithm's speed is not dependent on the element's location in the array (e.g.: Linear searching is slow if the element is at the end of the array).

Syntax-wise I would say this method tends toward writing "Hello, World!" four (or x depending on how it's scaled) times instead of using a repetition structure (e.g.: for... loop).


Now, this was all well and good, but I decided to go even further.

I asked what if could search more than (or less than) four indexes at once? The number of indexes queried each iteration specified by the user.

So I came up with this (again ported to C++):

#include <stdlib.h>

// Format each element of an (int) array.
void build(int array[], int length, int (&handler)(int element)) {
   int iterator = length;
   while (iterator) { iterator -= 1; array[iterator] = handler(array[iterator]); }
}

// Return a set of the multiples of Number ÷ Count lower than or equal to the Number.
int* step(int number, int count) {
    float difference = number / count;
    int* steps = (int*) malloc(20) /* This was an array literal in JavaScript but I think this counts... :P */;
    bool hasStepped = false;

    while (count) {
        steps[count -= 1] = (hasStepped ? steps[count + 1] : 0) + difference;
        hasStepped = true;
    }

     return steps;
}

/* Assert if an element is within an (int) array */
bool includes(int array[], int element, int length, int iterationStopCount = 4) {
    if (length == 1)
        return array[0] == element;

    else if (length) {
        int iterator = length;

        // Perform a Reversed Linear Search
        if (iterationStopCount == 1)
             while (iterator) if (array[iterator -= 1] == element) return true;

        // Perform what I call a "Gradient Search"
        else {
            /*
                This condition is here because I do not know
                the algorithm behaves otherwise.
            */
            if (iterationStopCount > length) iterationStopCount = length;

            bool hasRedundantIterations = length % iterationStopCount;
            int* iterationStops = step(length, iterationStopCount),
                iterationStopsLength = iterationStopCount;

            build(iterationStops, [](int step) { return step >> 0; });

            iterator -= iterationStops[1];
            iterationStops[0] = 0;

            if (iterator != -1)
            while (iterator) {
                int iterationStopsIterator = iterationStopsLength;

                iterator -= 1;

                while (iterationStopsIterator)
                if (array[iterator + iterationStops[iterationStopsIterator -= 1]] == element)
                    return true;
            }
        }
    }

    return false;
}

This method is exactly like the first code earlier, but indexes iterationStopCount elements at a time every iteration (From prior testing I found iterationStopCount = 4 to be the most performant).

Now, to address the elephant in this code.

Yes, the hasRedundantIndexes variable states that this algorithm can perform redundant checks (query an array index multiple times (twice at maximum)), but this only happens if the iterationStopCount is not a factor of the length of the array.


I call this method of searching arrays a Gradient Search because it:

  • Splits the array at various stops (indexes) and
  • Linear searches every stop's range each iteration (which has been reduced to avoid inaccuracy/ redundancy).

What I've done here could be (or is, I don't know) slower than Linear Searching or Binary Searching for ordered lists but I see it has merit because:

  • It does not need the list to be ordered.
  • It spends less time than the slowest speed of a Linear Search (e.g.: \$O(n)\$) since each iteration covers a broad scope of the array.

I would say it falls short for basic searches through minimal-sized arrays.


I want to now hand this to you: Does this method (what I called an algorithm) really have any advantage or utility?

If the method is efficient in its field, then I will use it further on for my personal projects; else I'll debunk it myself and forget about it.

\$\endgroup\$
  • 4
    \$\begingroup\$ Without trying to understand what your method does, let me just state that theoretically, you cannot beat a linear scan. Indeed, there is a linear lower bound for the problem and a matching upper bound is exhibited by a linear scan. Moreover, even in practice, scanning an array in a linear fashion is natural for modern hardware and thus very fast. \$\endgroup\$ – Juho Apr 6 at 16:31
  • 2
    \$\begingroup\$ this is tagged as both c and c++. Please pick one. They are different languages with different features and different idioms. \$\endgroup\$ – AGirlHasNoName Apr 6 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.