1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
/*
* Copyright (c) 2014 Tobias Klauser
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*/
#ifndef __BINSEARCH_CLOSEST_HPP__
#define __BINSEARCH_CLOSEST_HPP__
#include <vector>
/** Binary search for the closest value in a vector.
*
* This function assumes the vector to be sorted. If the value is outside
* the range of the vector, it is clamped accordingly. If several elements
* in the vector are equally close, the first one is returned.
*
* @param vec
* The sorted vector to search.
* @param val
* Scalar value for which to search the closest element in the vector.
* @return
* Index of the element in the vector that is closest to val or -1 if the
* vector contains no elements.
*/
template<typename T>
ssize_t binsearch_closest(const std::vector<T> vec, T val)
{
// empty vector
if (vec.size() < 1)
return -1;
// clamp value to range of vector
if (val < vec.at(0))
return 0;
if (val > vec.at(vec.size() - 1))
return vec.size() - 1;
size_t imin = 0;
size_t imax = vec.size() - 1;
while (imax - imin > 1) {
// determine midpoint, prevent integer overflow
size_t imid = imin + ((imax - imin) / 2);
if (vec.at(imid) >= val)
imax = imid;
else
imin = imid;
}
if (imax - imin == 1 && std::abs(vec.at(imax) - val) < std::abs(vec.at(imin) - val))
imin = imax;
return static_cast<ssize_t>(imin);
}
#endif /* __BINSEARCH_CLOSEST_HPP__ */
|
