分而治之阵算法++ [英] Divide and Conquer array algorithm ++

问题描述

我想实现一个功能，将看一个数组中的每个元素，并确定该特定元素不止一个INT和小于另一个INT更大。例如：

I'm trying to implement a function that will look at each element of an array and determine if that particular element is larger than one INT and less than another INT. For example:

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

我有这样一个基本的算法，它的作品，但我想创建一个更有效的一块code，使用分而治之的方法，但是我在使用递归的问题，使之计和我见过的所有例子只处理一个点的比较，而不是两个。任何人都可以摆脱对局势的一些情况。 （http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm）

I have this as a basic algorithm, which works but I want to create a more efficient piece of code, by using the 'divide and conquer' methodology, however I'm having problems using recursion to make it count and all examples I've seen only deal with one point of comparison, not two. can anyone shed some light on the situation. (http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm)

我原来的code（线性）：

My original code (linear):

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

例如$ C $从多个小时的工作在不同的东西，并用不同的例子code后，我所捡到的这至今（没有运气C：

Example code from what I've picked up of this so far(with no luck after many hours of working on various things, and using different example code:

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])

如果这个问题不明确对不起，不要问，如果你需要我详细说明什么。

If this question is not clear I'm sorry, do ask if you need me to elaborate on anything.

推荐答案

假设你输入向量的总是的排序，我觉得这样的事情可能会为你工作。这是我能想出的最简单的形式，而且性能是O（log n）的：

Assuming your input vector is always sorted, I think something like this may work for you. This is the simplest form I could come up with, and the performance is 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 将被视为福音，therfore的的任何输入值的调用，其中 LVAL＆GT; uval 应该返回false（因为这是不可能的），你可以删除的std :: MIN（）和的std :: MAX（）扩展。在这两种情况下，你还可以通过提高性能的outter前端装载机和pre-检查 LVAL 的顺序和 uval 要么（一）立即返回假，如果绝对顺序是必需的， LVAL＆GT; uval ，或（b）predetermine LVAL和uval在正确的顺序，如果范围 - 差分的要求。两个这样outter包装的例子如下探讨：

This uses implied range differencing; i.e. it always uses the lower of the two values as the lower-bound, and the higher of the two as the upper-bound. If your usage mandates that input values for lval and uval are to be treated as gospel, and therfore any invoke where lval > uval should return false (since it is impossible) you can remove the std::min() and std::max() expansions. In either case, you can further increase performance by making an outter front-loader and pre-checking the order of lval and uval to either (a) returning immediately as false if absolute ordering is required and lval > uval, or (b) predetermine lval and uval in proper order if range-differencing is the requirement. Examples of both such outter wrappers are explored below:

// 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 。进行到有望覆盖主要和边缘情况的单元测试都低于以及输出结果。

I have left the one I think you want as inRange. The unit tests performed to hopefully cover main and edge cases are below along with the resulting output.

#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

这篇关于分而治之阵算法++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！