Find the nearest/closest value in a sorted List
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];
}
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.