Алгоритм разделения и завоевания массива ++
Я пытаюсь реализовать функцию, которая будет смотреть на каждый элемент массива и определять, если этот конкретный элемент больше, чем один 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])
Если этот вопрос не ясен, извините, спросите, не нужно ли мне уточнить что-нибудь.
Решение
Предполагая, что ваш входной вектор всегда Сортировка, я думаю, что-то вроде этого может работать для вас. Это самая простая форма, которую я мог придумать, а производительность равна 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
Другие решения
Это на самом деле довольно просто, если вы предполагаете, что массив будет отсортирован. Вы можете избавиться от логарифмической сложности, всегда глядя на соответствующую левую или правую часть последовательности:
#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));
Насколько я понимаю, используя разделяй и властвуй для вашей конкретной проблемы
не принесет пользы. Однако, по крайней мере, в вашем примере, ввод
сортировать; Это можно улучшить, пропустив значения, пока не будет достигнута нижняя граница.