Boost: having an array of ints and some special int how to find nearest to yours in array?

So I hava an unsorted array of 30 ints like 340, 6401 1280, and so on random numbers. I have int x which was cined by user. I need to find which value in array is ne开发者_JAVA百科arest down (lower, smaller,less) to that x value. How to do such thing?

If the array is unsorted and you do only one query then the fastest way is just to scan through the whole array. If you do asymptotically more queries than the size of the array than you should sort the array first and then do binary searches for each query.

Sort your array (or use an std::set) and check out std::lower_bound.

You could use std::max_element() with a custom comparison operator:

struct limited_cmp {
   int limit;
   limited_cmp(int a_limit) : limit(a_limit) {
   }
   bool operator()(int left, int right) const {
      if (left <= limit && limit < right) {
         return false;
      }
      return (left < right);
   }
};

int main() {
   std::vector<int> numbers = ...;
   std::cout << "nearest is "
         << *std::max_element(numbers.begin(), numbers.end(), limited_cmp(5))
         << std::endl;   
}

If all you have is an array of unordered ints, you can't do better than an O(n) pass through the array. You can do it in O(logn) using binary search if you're willing to pay the cost of sorting the array upfront.

I don't think there are any algorithms in boost that will do this for you though.