Find the nearest/closest value in a sorted List [duplicate]

Question

I was wondering if it is possible to find the closest element in a sorted List for a element that is not in the list.

For example if we had the values [1,3,6,7] and we are looking for the element closest to 4, it should return 3, because 3 is the biggest number in the array, that is smaller than 4.

I hope it makes sense, because English is not my native language.

Answer 1

Because the collection is sorted, you can do a modified binary search in 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];     } 

Since most of the code above is binary search, you can leverage the binarySearch(...) provided in the std library and examine the value of the insertion point:

    public static int usingBinarySearch(int value, int[] a) {         if (value <= a[0]) { return a[0]; }         if (value >= a[a.length - 1]) { return a[a.length - 1]; }          int result = Arrays.binarySearch(a, value);         if (result >= 0) { return a[result]; }          int insertionPoint = -result - 1;         return (a[insertionPoint] - value) < (value - a[insertionPoint - 1]) ?                 a[insertionPoint] : a[insertionPoint - 1];     }  

Answer 2

You need Array.binarySearch, docs.

Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key.