1

假设下一个数组：

int a[] = new int[15];

每个值都是数据库中某个时期内特定状态下某些天的计数器。示例：期间 1/1/2000 - 1/3/2000（3 天，而不是 3 个月）：状态XXXXX的天数。

我想要做的是检查对象计数与网站上的对象计数相比是否正确。如果网站未加载，搜索本身最多需要几秒钟。

我做了一个非常简单的测试项目，将 a 的值与另一个数组上的一些固定值进行比较，我随机选择了一些不同的值，实际上 15 个中有 7 个是不同的。

当前实现的算法是二分搜索。这段代码的输出是正确的，但是对于提供的数据，在真实应用程序上将发生的搜索次数为 144，这根本没有效率。是否有任何其他算法可以用来最小化搜索次数（或本例中的汇总计算）？

重要提示：这些时间段可以大到 2010 年 9 月 1 日 - 今天，因此暂时不能单独搜索每一天。

如果需要，请向我寻求解释。

    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);
    }
4

2 回答 2

1

您不能在这里使用二进制搜索，因为您需要检查每个 [start, end] 组合。此外，如果您使用二进制搜索在两个方向上进行搜索，则无论如何它都不是二进制搜索。

我建议以下解决方案：

// 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;
    }   
}

这在 O([n(n-1)] / 2) 中运行（如果我没记错的话），在最坏的情况下是 O(n²)。由于您必须检查所有 [start, end] 组合，因此您无法以较小的数量级解决此问题。

编辑：前提是我理解了你的问题。

于 2012-11-14T10:41:28.427 回答
0 
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]);
}

正如我在评论中所说，您只需要在两个数组的每个位置之间进行简单比较。

于 2012-11-14T11:08:06.347 回答