C > Find the closest value in an array (double type) > v0.1
0
動作環境
C++ Builder XE4
background
- Get elements of close value with TDateTime type (as double type) in C++ Builder
- Let's do it with a binary search
information
In the first place, it is not our own implementation, but it is already there, isn't it?
-
https://cpprefjp.github.io/reference/algorithm/binary_search.html
- Dichotomy
- The return value is of type bool and the index is not known
Let's implement it ourselves.
-
https://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search
- Implementation in various languages
- Referenced by C implementation
- However, this is an int search, not a double type
- I considered the double type by myself
Implementation v0.1
It is for C++, but I tried to implement it as C. (Is it also used in embedding?)
#include <stdio.h>
int BinarySearch(double *vals, int size, double ref);
int main(void) {
// list to be searched (sorted)
double vals[] = { 2.718, 3.14, 6.022, 10.23 };
int size = sizeof(vals)/sizeof(vals[0]);
// list where each value is searched
double chks[] = { 2.0, 3.13, 3.14, 3.15, 15.0 };
int num = sizeof(chks)/sizeof(chks[0]);
for(int idx=0; idx<num; idx++) {
int pos = BinarySearch(vals, size, chks[idx]);
if (pos >= 0) {
printf("pos = %d, %f for %f\
", pos, vals[pos], chks[idx]);
} else {
printf("not found for %f\
", chks[idx]);
}
}
return 0;
}
int BinarySearch(double *vals, int size, double target) {
int start = 0;
int end = size - 1;
int mid;
if (target < vals[start] || target > vals[end]) {
return -1;
}
while (start <= end) {
mid = (start + end) / 2;
if (mid == (start+1) && (target >= vals[start]) && (target < vals[mid])) {
return start;
} else if (target < vals[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
if (end < start) {
return end;
}
return start;
}
Example of operation
For { 2.718, 3.14, 6.022, 10.23 }
not found for 2.000000
pos = 0, 2.718000 for 3.130000
pos = 1, 3.140000 for 3.140000
pos = 1, 3.140000 for 3.150000
not found for 15.000000
remarks
I could do that.
Variable names are appropriate, so consider a little more when actually using them
In the first place
Isn't there a function in the library that behaves the desired behavior in a C++ or C++ Builder library?
Haven't found it.
relation
Here's what I found in the Delphi implementation
