問題

有如下一堆有序數(shù)據(jù)：

數(shù)據(jù)描述：

1. 有序：從小到大
2. 對每個數(shù)字進行編號：0 1 2 3

那么如何快速找到你想要的數(shù)據(jù)？

1. 數(shù)字在集合中

建議分而治之，二分查找。

2. 數(shù)字不再集合中，但要找到跟它最接近的。

建議分而治之，二分查找。
為什么要二分查找??？

速度快啊。

代碼如何實現(xiàn)呢？

上一個是，一個數(shù)和一個數(shù)比較。
我們現(xiàn)在只需要考慮，一個數(shù)和兩個數(shù)相比較。

**取中間的兩個數(shù)：**

看目標(biāo)的數(shù)字到 兩個數(shù)之間的距離情況。

1. 離 3.6 更近，則繼續(xù)處理 3.6 左邊的數(shù)據(jù)。
2. 離 5.4 更近，則繼續(xù)處理 3.6 右邊的數(shù)據(jù)。

代碼

我的：

 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;
    }