在排序列表中找到最接近/最接近的值

Question

我想知道是否有可能找到一个最接近的元素List的元素 ，是不是 在那里。

例如，如果我们具有[1,3,6,7]值，并且正在寻找最接近4的元素，则它应返回3，因为3是数组中的最大数字，小于4。

我希望这是有道理的，因为英语不是我的母语。

Answer 1

如果数组已排序，则可以在以下位置进行修改的二进制搜索O( log n )：

    public static int search(int value, int[] a) {

        if(value < a[0]) {
            return a[0];
        }
        if(value > a[a.length-1]) {
            return a[a.length-1];
        }

        int lo = 0;
        int hi = a.length - 1;

        while (lo <= hi) {
            int mid = (hi + lo) / 2;

            if (value < a[mid]) {
                hi = mid - 1;
            } else if (value > a[mid]) {
                lo = mid + 1;
            } else {
                return a[mid];
            }
        }
        // lo == hi + 1
        return (a[lo] - value) < (value - a[hi]) ? a[lo] : a[hi];
    }