Алгоритм массива «разделяй и властвуй» ++

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

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