c++ - 分而治之数组算法++

我正在尝试实现一个函数，该函数将查看数组的每个元素并确定该特定元素是否大于一个INT并小于另一个INT。例如:

Return true if Arr[5] is >i && < u

我将其作为一种基本算法，可以工作，但是我想通过使用“分而治之”的方法来创建更有效的代码，但是我在使用递归使其计数以及我拥有的所有示例时遇到了问题看到只处理一个比较点，而不是两个。任何人都可以对情况有所了解。
(http://zh.wikipedia.org/wiki/Divide_and_conquer_algorithm)

我的原始代码(线性):

int SimpleSort(int length)
{
    int A[] = {25,5,20,10,50};
    int i = 25; //Less Than int
    u = 2; //Greater Than
    for(int Count = 0; Count < length; Count++) //Counter
    {
        if (A[Count] <= i && A[Count] >= u) //Checker
            return true;
    } return false;
}

到目前为止，我已经从示例代码中提取了示例代码(在花了很多时间处理各种事情并使用不同的示例代码之后，还是没有运气:

int A[] = {5,10,25,30,50,100,200,500,1000,2000};
int i = 10; //Less Than
int u = 5;  //Greater Than


int min = 1;
int max = length;
int mid = (min+max)/2;

if (i < A[mid] && u > A[mid])
{
    min = mid + 1;

}
else
{
    max = mid - 1;
}
Until i <= A1[mid] && u >= A1[mid])

如果这个问题不清楚，很抱歉，请问您是否需要我详细说明。

最佳答案

假设您的输入 vector 总是经过排序的，那么我认为这样的方法可能对您有用。这是我能想到的最简单的形式，其性能为O(log n):

bool inRange(int lval, int uval, int ar[], size_t n)
{
    if (0 == n)
        return false;

    size_t mid = n/2;
    if (ar[mid] >= std::min(lval,uval))
    {
        if (ar[mid] <= std::max(lval,uval))
            return true;
        return inRange(lval, uval, ar, mid);
    }
    return inRange(lval, uval, ar+mid+1, n-mid-1);
}

这使用了隐式范围差异；即，它始终使用两个值中的较低者作为下界，而使用两个中较高者作为上限。如果您的用法要求将lval和uval的输入值视为福音，并且在lval > uval应该返回false的任何调用之前(因为不可能)，则可以删除std::min()和std::max()扩展。在这两种情况下，您都可以通过以下方式进一步提高性能:制作一个外部前置装载器，并预先检查lval和uval的顺序为(a)如果需要绝对排序，则立即返回false，然后返回lval > uval；或者(b)预先确定lval和如果需要范围差异，则以正确的顺序排列。下面介绍了这两种外包装的示例:

// search for any ar[i] such that (lval <= ar[i] <= uval)
//  assumes ar[] is sorted, and (lval <= uval).
bool inRange_(int lval, int uval, int ar[], size_t n)
{
    if (0 == n)
        return false;

    size_t mid = n/2;
    if (ar[mid] >= lval)
    {
        if (ar[mid] <= uval)
            return true;
        return inRange_(lval, uval, ar, mid);
    }
    return inRange_(lval, uval, ar+mid+1, n-mid-1);
}

// use lval and uval as an hard range of [lval,uval].
//  i.e. short-circuit the impossible case of lower-bound
//  being greater than upper-bound.
bool inRangeAbs(int lval, int uval, int ar[], size_t n)
{
    if (lval > uval)
        return false;
    return inRange_(lval, uval, ar, n);
}

// use lval and uval as un-ordered limits. i.e always use either
// [lval,uval] or [uval,lval], depending on their values.
bool inRange(int lval, int uval, int ar[], size_t n)
{
    return inRange_(std::min(lval,uval), std::max(lval,uval), ar, n);
}

我已经把我想保留的那个留给inRange了。希望能够涵盖主要案例和边缘案例的单元测试以及结果输出如下。

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <iterator>

int main(int argc, char *argv[])
{
    int A[] = {5,10,25,30,50,100,200,500,1000,2000};
    size_t ALen = sizeof(A)/sizeof(A[0]);
    srand((unsigned int)time(NULL));

    // inner boundary tests (should all answer true)
    cout << inRange(5, 25, A, ALen) << endl;
    cout << inRange(1800, 2000, A, ALen) << endl;

    // limit tests (should all answer true)
    cout << inRange(0, 5, A, ALen) << endl;
    cout << inRange(2000, 3000, A, ALen) << endl;

    // midrange tests. (should all answer true)
    cout << inRange(26, 31, A, ALen) << endl;
    cout << inRange(99, 201, A, ALen) << endl;
    cout << inRange(6, 10, A, ALen) << endl;
    cout << inRange(501, 1500, A, ALen) << endl;

    // identity tests. (should all answer true)
    cout << inRange(5, 5, A, ALen) << endl;
    cout << inRange(25, 25, A, ALen) << endl;
    cout << inRange(100, 100, A, ALen) << endl;
    cout << inRange(1000, 1000, A, ALen) << endl;

    // test single-element top-and-bottom cases
    cout << inRange(0,5,A,1) << endl;
    cout << inRange(5,5,A,1) << endl;

    // oo-range tests (should all answer false)
    cout << inRange(1, 4, A, ALen) << endl;
    cout << inRange(2001, 2500, A, ALen) << endl;
    cout << inRange(1, 1, A, 0) << endl;

    // performance on LARGE arrays.
    const size_t N = 2000000;
    cout << "Building array of " << N << " random values." << endl;
    std::vector<int> bigv;
    generate_n(back_inserter(bigv), N, rand);

    // sort the array
    cout << "Sorting array of " << N << " random values." << endl;
    std::sort(bigv.begin(), bigv.end());

    cout << "Running " << N << " identity searches..." << endl;
    for (int i=1;i<N; i++)
        if (!inRange(bigv[i-1],bigv[i],&bigv[0],N))
        {
            cout << "Error: could not find value in range [" << bigv[i-1] << ',' << bigv[i] << "]" << endl;
            break;
        };
    cout << "Finished" << endl;

    return 0;
}

输出结果:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
Sorting array of 2000000 random values.
Running 2000000 identity searches...
Finished

关于c++ - 分而治之数组算法++，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13284503/