Divide and Conquer array algorithm ++

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

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

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

Output Results:

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's actually pretty straight forward if you assume the array to be sorted. You can get away with logarithmic complexity by always looking at either the respective left or right side of the sequence:

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

You can invoke this for plain arrays with:

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

To my understanding, using divide and conquer for your specific problem will not yield an andvantage. However, at least in your example, the input is sorted; is should be possible to improve a bit by skipping values until your lower bound is reached.