问题
有如下一堆有序数据：
数据描述：
- 有序：从小到大
- 对每个数字进行编号：0 1 2 3
那么如何快速找到你想要的数据？
1. 数字在集合中
建议分而治之，二分查找。
2. 数字不再集合中，但要找到跟它最接近的。
建议分而治之，二分查找。
为什么要二分查找啊？
速度快啊。
代码如何实现呢？
上一个是，一个数和一个数比较。
我们现在只需要考虑，一个数和两个数相比较。
**取中间的两个数：**
看目标的数字到 两个数之间的距离情况。
- 离 3.6 更近，则继续处理 3.6 左边的数据。
- 离 5.4 更近，则继续处理 3.6 右边的数据。
代码
我的：
public static int getEntryIndex1(List<Unit> mValues, float xValue, Rounding rounding) {
if (mValues == null || mValues.isEmpty())
return -1;
int low = 0;
int high = mValues.size() - 1;
while (low < high) {
int m = (low + high) / 2;
float f1 = mValues.get(m).getX();
float f2 = mValues.get(m + 1).getX();
if (xValue >= f1 && xValue <= f2) {
float d1 = Math.abs(xValue - f1);
float d2 = Math.abs(xValue - f2);
if (d1 <= d2) {
low = m;
} else {
high = m + 1;
}
break;
} else if (xValue < f1) {
high = m;
} else if (xValue > f2) {
low = m;
}
}
int result = low;
if (rounding == Rounding.UP) {
result = high;
} else if (rounding == Rounding.DOWN || rounding == Rounding.CLOSEST) {
result = low;
}
return result;
}
MpAndroidChart:
public static int getEntryIndex(List<Unit> mValues, float xValue, Rounding rounding) {
if (mValues == null || mValues.isEmpty())
return -1;
int low = 0;
int high = mValues.size() - 1;
while (low < high) {
int m = (low + high) / 2;
final float d1 = mValues.get(m).getX() - xValue,
d2 = mValues.get(m + 1).getX() - xValue,
ad1 = Math.abs(d1), ad2 = Math.abs(d2);
if (ad2 < ad1) {
// [m + 1] is closer to xValue
// Search in an higher place
low = m + 1;
} else if (ad1 < ad2) {
// [m] is closer to xValue
// Search in a lower place
high = m;
} else {
// We have multiple sequential x-value with same distance
if (d1 >= 0.0) {
// Search in a lower place
high = m;
} else if (d1 < 0.0) {
// Search in an higher place
low = m + 1;
}
}
}
if (high != -1) {
float closestXValue = mValues.get(high).getX();
if (rounding == Rounding.UP) {
if (closestXValue < xValue && high < mValues.size() - 1) {
++high;
}
} else if (rounding == Rounding.DOWN) {
if (closestXValue > xValue && high > 0) {
--high;
}
}
}
return high;
}
