   Fast Algorithm to return closest hit in vector
  HiI am trying to find a fast algorithm(binary search kindof fast) for the following simple problem. I want to search for x in a vector & get back the closest number to x that exists in the vector(or if x exists in vector then get x back).For example :int a = {10,20,30,30,50,60};vector <int> list(a,6);int closestMatch = FindClosestMatch(list,24); And so closestMatch should equal 20.I looking to either write my own in c++ or use an existing one. For example I know that in the algorithm library there is upper_bound & lower_bound. But I think they dont return the closest match but the upper or lower match, is that correct or are they what I am looking for? I'm pretty familiar with a binary search but I am under the impression they can only return an exact match, not the closest number to the queried number, is that correct? If not can you give me some advice on how I alter a binary search to return the closest match?binary search - can I alter it to find the closest match?:int binarySearch(vector <int>list, int first, int last, int key) { while (first <= last) {  int mid = (first + last) / 2;if (key > list.at(mid))  first = mid + 1;    else if (key < list.at(mid))  last = mid - 1;  else return mid;    }   return -1; // failed to find key}
int findClosest(std::vector<int>& list, int first, int last, int key) {   while (first <= last) {  int mid = (first + last) / 2;if (key > list.at(mid))  first = mid + 1;    else if (key < list.at(mid))  last = mid - 1;  else return mid;    }   return (abs(list.at(first) - key) < abs(list.at(last) - key)) ?  list.at(first) : list.at(last);}(think that's right...)   ;  std::lower_bound will do the job. [EDIT: use std::equal_range instead if there's the possibility of duplicate elements]The closest value will be either the element corresponding to returned iterator, or the following element (assuming end() is not returned).Don't write your own binary search.   ;  ZOMG im teh 10% !!1Seriously, I'm quite surprised that this algorithm needed to be "discovered".EDIT: maybe I'm wrong. I only did a similar stuff (huhh I don't even know the terms I just do things, I'm that good ;)   ;Quote:Original post by the_eddThe closest value will be either the element corresponding to returned iterator, or the following element (assuming end() is not returned).You mean the previous element, right?;  Thanks for the replies guys, I checked out that lower_bound() again but it is not returning the closest match. I thought that there would be a function in algorithm to do this sort of thing?Thanks to jwezorek for helping with the binary search. I would like to find out if there is a c++ library function for this, this is the first time ever I have come across something that does not already exist in c++ :P   ;Quote:Original post by grettyThanks for the replies guys, I checked out that lower_bound() again but it is not returning the closest match.Are you comparing the returned value with its neighbour? lower_bound will return the first position where you would insert your value if you want to preserve the ordering.For example: if your list is {10,20,30,40,50,60}, then lower_bound for 24 will be index 2 (30), since that's the index at which you would insert the number 24. Now you need to compare the number 24 with its two neighbours, 20 and 30, to see which one is the closest one. So once you've got an index from lower_bound you need to get the value at index - 1 as well, unless the index is begin, and then compare the two with your value to see which one is the closest one.   