94 lines
3.2 KiB
C++
94 lines
3.2 KiB
C++
#pragma once
|
|
namespace renderive {
|
|
#define LOWER(offset) l_lower(spaces[offset])
|
|
#define UPPER(offset) l_upper(spaces[offset])
|
|
template <typename T>
|
|
int binary_search(double value, T** spaces, int space_size, std::function<double(T*)>& l_lower, std::function<double(T*)>& l_upper) {
|
|
int start_index = 0, end_index = space_size - 1;
|
|
if (start_index == end_index)
|
|
return start_index;
|
|
double min = LOWER(start_index), max = UPPER(end_index);
|
|
if (value < min) {
|
|
// qDebug() << QString("warnning binary_search value:%1 < %2").arg(value).arg(min);
|
|
return start_index;
|
|
}
|
|
if (value > max) {
|
|
// qDebug() << QString("warnning binary_search value:%1 > %2").arg(value).arg(max);
|
|
return end_index;
|
|
}
|
|
while (start_index != end_index) {
|
|
if (start_index + 1 == end_index) {
|
|
double mid = (UPPER(start_index) + LOWER(end_index)) / 2.0;
|
|
if (value < mid)
|
|
return start_index;
|
|
return end_index;
|
|
}
|
|
int m = (start_index + end_index) / 2;
|
|
double lower = m != 0 ? (UPPER(m - 1) + LOWER(m)) / 2.0 : min;
|
|
double upper = m != space_size - 1 ? (UPPER(m) + LOWER(m + 1)) / 2.0 : max;
|
|
// qDebug() << " lower == " << lower << " upper == " << upper << "midIndex == " << m << " value == " << value;
|
|
// qDebug() << " start_index == " << start_index << " end_index == " << end_index;
|
|
if (value < lower) {
|
|
end_index = m;
|
|
}
|
|
else if (value > upper) {
|
|
start_index = m;
|
|
}
|
|
else {
|
|
return m;
|
|
}
|
|
}
|
|
qDebug() << QString("warnning start_index:%1, end_index:%2").arg(start_index).arg(end_index);
|
|
return start_index;
|
|
}
|
|
#undef LOWER
|
|
#undef UPPER
|
|
static int binary_search(double value, const std::vector<double>& data, bool& ok) {
|
|
if (data.empty()) {
|
|
ok = false;
|
|
return -1; // 返回 -1 表示数组为空
|
|
}
|
|
// 判断排序顺序
|
|
bool ascending_order = data[0] < data[data.size() - 1];
|
|
int left = 0;
|
|
int right = data.size() - 1;
|
|
// 二分查找
|
|
while (left <= right) {
|
|
int mid = left + (right - left) / 2;
|
|
if (mid < data.size() - 1) {
|
|
if (ascending_order) {
|
|
if (data[mid] <= value && data[mid + 1] > value) {
|
|
ok = true;
|
|
return mid;
|
|
}
|
|
else if (data[mid] < value) {
|
|
left = mid + 1;
|
|
}
|
|
else {
|
|
right = mid - 1;
|
|
}
|
|
}
|
|
else {
|
|
// 处理降序排列的情况
|
|
if (data[mid] >= value && data[mid + 1] < value) {
|
|
ok = true;
|
|
return mid;
|
|
}
|
|
else if (data[mid] > value) {
|
|
left = mid + 1;
|
|
}
|
|
else {
|
|
right = mid - 1;
|
|
}
|
|
}
|
|
}
|
|
else {
|
|
break; // 如果 mid 已经是最后一个元素，不再继续查找
|
|
}
|
|
}
|
|
ok = false;
|
|
// 如果找不到，则返回 -1，表示 value 不在区间内
|
|
return -1;
|
|
}
|
|
} // namespace renderive
|