Most effective search algorithm to find multiple incorrect values in an array

Question

Suppose the next array:

int a[] = new int[15];

Each value is a counter of some days in a specific state in a period in a database. Example: Period 1/1/2000 - 1/3/2000 (3 days, not 3 months): Number of days in state XXXXX.

What I want to do is check if the objects count is correct compared to the objects count on a website. The search itself takes some seconds at best if the website is not loaded.

I had made a very simple test project which compares the values of a with some fixed values on another array and I randomly chose some values to be different, in fact 7 out of 15 were different.

The current algorithm implemented is binary search. The output of this piece of code is correct, but the number of searches that would occur on the real application is 144 for the data provided, which is not efficient at all. Is there any other algorithm that I could use to minimize the number of searches (or summary calculations in this example)?

IMPORTANT NOTE: The periods can be as large as Sep 1, 2010 - Today, so for the moment searching each day independently is not an option.

Ask me for explanations if needed.

    a = new int[15];
    b = new int[15];
    searchCount = 0;

    // Fill a and b with some test values
        a[0] = 12;
        a[1] = 13;
        a[2] = 26;
        a[3] = 30;
        a[4] = 6;
        a[5] = 3;
        a[6] = 1;
        a[7] = 2;
        a[8] = 8;
        a[9] = 12;
        a[10] = 19;
        a[11] = 21;
        a[12] = 56;
        a[13] = 100;
        a[14] = 80;

        b[0] = 11;
        b[1] = 9;
        b[2] = 26;
        b[3] = 30;
        b[4] = 8;
        b[5] = 3;
        b[6] = 1;
        b[7] = 5;
        b[8] = 8;
        b[9] = 13;
        b[10] = 19;
        b[11] = 21;
        b[12] = 55;
        b[13] = 99;
        b[14] = 80;
    // Filled.

    void BinarySearch(int start, int end)
    {
        if (AreSumsEqual(start, end))
        {
            Debug.WriteLine("Values from positions" + start + " to " + end + " are ok");
        }
        else if (start == end)
        {
            Debug.WriteLine("Value at position " + start + " is not ok");
        }
        else
        {
            int mid = Middle(start, end);
            BinarySearch(start, mid - 1);
            BinarySearch(mid, end);
        }
    }

    int Middle(int start, int end)
    {
        return (int)Math.Ceiling((start + end) / 2.0);
    }

    bool AreSumsEqual(int start, int end)
    {
        bool areEqual = false;
        int sumA = 0;
        int sumB = 0;
        for (int i = start; i <= end; i++)
        {
            sumA += a[i];
            sumB += b[i];
            searchCount += 2; // Each sum calculated is the same as one 
            // website search. This takes the most time in real application, so
            // repeat it as few times as possible.
        }

        return areEqual = (sumA == sumB);
    }

Answer 1

You can't use binary search here, since you need to check every [start, end] combindation. Also, if you search in both directions with binary search, it is not binary search anyway.

I'd suggest the following solution:

// Remove this, if you want all matches
bool found = false;

for (int start = 0; start < a.count; start++)
{
      // Maybe you need end = start + 1, not sure
    for (int end = start; end < a.count; end++)
    {
        if (AreSumsEqual(start, end)
        {
            // Found! Let's break to avoid useless iterations,
            // if we only want one match.
            found = true;
            break;
        }
    }

    if (found)
    {
        break;
    }   
}

This runs in O([n(n - 1)] / 2) (if I'm not mistaken) which is O(n²) in the worst case. Since you have to check all all [start, end] combinations, you can't solve this with a smaller order of magnitude.

EDIT: This is provided I understood your question.

Answer 2

var SearchResults = a.Select((value, index) => a[index] == b[index]);

for (int i=0;i<a.Length;i++)
{
  Debug.WriteLine("Values in position {0} are {1}", i, SearchResults.ToList()[i]);
}

As i said in the comments, you just need a simple comparison between each position on two arrays.