CODEWITHSUNDEEP
c++arrayssearch
F.Hand
F.Hand

Reputation: 83

C++ - Searching in array from both sides

Is there any difference in speed between first loop and a second one when it comes to speed of executing it? Im talking also about larger arrays than this sample one.

int main()
{
    int n = 17;
    int posz = 7;
    int array[] = {0, 1, 9, 2, 8, 3, 8, 5, 4, 7, 6, 10, 23, 43, 123, 54, 76, 34};
    for (int i = 0; i < (n / 2) + 1; i++)
    {
        if (array[i] == posz || array[n - 1 - i] == posz)
        {
            std::cout << "found\n";
            break;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (array[i] == posz)
        {
            std::cout << "found\n";
            break;
        }
    }

    return 0;
}

Upvotes: 1

Views: 255

Answers (1)

deadbird11
deadbird11

Reputation: 141

In terms of Big-O time, no, since both methods are O(n).

In the first loop, you iterate less times but do more calculations per iteration. In the second loop, you do less calculations per iteration but do more iterations overall. I wouldn't expect there to be any huge performance difference between the two, and the compiler might even change the two to be the same if you step through the assembly code.

It would also depend on the caching scheme your CPU is using, since in a large enough array the first loop may cache two blocks of memory rather than the second which would only cache one. This could have adverse effects on a direct-mapped cache, since the high and low indexes might refer to memory locations that occupy the same cache block, so accessing one after the other would result in constant cache misses.

At this point, it really is just up to what is more clear about what you are trying to accomplish, so I'd recommend loop #2. Not to mention, the second approach is far less error prone.

Upvotes: 4

Related Questions