Алгоритм разделения и завоевания массива ++

Я пытаюсь реализовать функцию, которая будет смотреть на каждый элемент массива и определять, если этот конкретный элемент больше, чем один INT и меньше, чем другой INT. Например:

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

У меня есть базовый алгоритм, который работает, но я хочу создать более эффективный кусок кода, используя методологию «разделяй и властвуй», однако у меня возникают проблемы с использованием рекурсии, чтобы подсчитать ее, и во всех примерах видел только дело с одной точкой сравнения, а не с двумя. может кто-нибудь пролить свет на ситуацию.
(Http://en.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 Thanint 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])

Если этот вопрос не ясен, извините, спросите, не нужно ли мне уточнить что-нибудь.

2

Решение

Предполагая, что ваш входной вектор всегда Сортировка, я думаю, что-то вроде этого может работать для вас. Это самая простая форма, которую я мог придумать, а производительность равна 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 либо (а) возвращать сразу как ложь, если требуется абсолютный порядок и lval > uvalили (b) предварительно определить lval и uval в правильном порядке, если требуется различие в диапазоне. Примеры обоих таких внешних упаковщиков рассматриваются ниже:

// 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
3

Другие решения

Это на самом деле довольно просто, если вы предполагаете, что массив будет отсортирован. Вы можете избавиться от логарифмической сложности, всегда глядя на соответствующую левую или правую часть последовательности:

#include <iterator>

template <typename Limit, typename Iterator>
bool inRange(Limit lowerBound, Limit upperBound, Iterator begin, Iterator end) {
if (begin == end) // no values => no valid values
return false;
Iterator mid = begin;
auto const dist = std::distance(begin,end);
std::advance(mid,dist/2); // mid might be equal to begin, if dist == 1
if (lowerBound < *mid && *mid < upperBound)
return true;
if (dist == 1) // if mid is invalid and there is only mid, there is no value
return false;
if (*mid > upperBound)
return inRange(lowerBound, upperBound, begin, mid);
std::advance(mid,1); // we already know mid is invalid
return inRange(lowerBound, upperBound, mid, end);
}

Вы можете вызвать это для простых массивов с:

inRange(2,25,std::begin(A),std::end(A));
1

Насколько я понимаю, используя разделяй и властвуй для вашей конкретной проблемы
не принесет пользы. Однако, по крайней мере, в вашем примере, ввод
сортировать; Это можно улучшить, пропустив значения, пока не будет достигнута нижняя граница.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector