Find the nearest/closest value in a sorted List [duplicate]
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.
Do you want the closest number (which might be larger) or the closest number less than the query value?
So, what would be the outcome for having 3 and 5 (in your case). You choose the lower one because there were no upper closer. but what if you have those two?
Iterate through the list until you find the first value, which is bigger than your x or the the end of the list is reached. Then check the last two values.
8 Answers 8
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 else if (value > a[mid]) < lo = mid + 1; >else < return a[mid]; >> // lo == hi + 1 return (a[lo] - value)
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 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)
Eventhough is has a little «bug» when the element that is supposed to be the result, happens to be the one before the last one, the result comes as the last one insted. any idea why that is? For example in the array if the number is 10 and the array is <1,3,5,7,9,11>the result comes as 11 which is wrong, but if the array is the result comes as 9, which is the correct one! Any idea ?
the bug in this code is the last return statement. At the end of the loop, lo points to the ceil and hi points to the floor of the key (due to the while condition check). Hence the correct return statement will be: return (a[lo] — value) < (value - a[hi]) ? a[lo] : a[hi] ;
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.
Yeah thanks for the suggestion, but I thought if there was a way without using anything like that. For example I tried modifying the binarysearch method..but I had no luck so far
Considering using NavigableSet , in particular higher and lower .
Andrey’s answer is correct. Just expanding on it a bit.
No need to reinvent the wheel when you can use the built in binary search.
You can find the indices with:
int leftIndex = (-Collections.binarySearch(allItems, key) - 2); int rightIndex = (-Collections.binarySearch(allItems, key) - 1); The item in the list will need to implement Comparable. Simple types like String and Integer already implement this. Here’s an example https://www.javatpoint.com/Comparable-interface-in-collection-framework.
Depending on your use case you may want to do index = Math.max(0, index) after the binary search just to be safe.
Update: As pointed out by sundar, if there are duplicates in the array then binary search will not return accurate results. So perhaps if binary search fails then you can default to a linear search.
There are two methods to achieve the result-
I prefer to use the lower_bound method, it’s short 🙂
int pos=lower_bound(v.begin(),v.end(),value); if(pos!=0&&target!=v[pos]) if(abs(v[pos]-value)>abs(value-v[pos-1])) pos=pos-1; For binary search, you can refer to the above answers, as my code will seem like a copy paste of their code. Note that I have declared the array globally here.
binarysearch(int low,int high,int val) < if(val<=arr[0]) return 0; if(val>=arr[n-1]) return arr[n-1]; while(low<=high) < int mid=(low+high)/2; if(v[mid]>val) return binarysearch(low,mid-1,val); else if(v[mid] if(abs(val-v[low])>=abs(val-v[high])) return high; else return low; > Just thinking off the top of my head, if you need to find all closest values in a sorted list, you can find a closest value, then find all values with the same distance away from the target. Here, I use binary search 3 times:
- First to find a closest value
- Second to find the left-most closest value
- Third to find the right-most closest value
def closest_value(arr, target): def helper(arr, target, lo, hi, closest_so_far): # Edge case if lo == hi: mid = lo if abs(arr[mid] - target) < abs(arr[closest_so_far] - target): closest_so_far = mid return closest_so_far # General case mid = ((hi - lo) >> 1) + lo if arr[mid] == target: return mid if abs(arr[mid] - target) < abs(arr[closest_so_far] - target): closest_so_far = mid if arr[mid] < target: # Search right return helper(arr, target, min(mid + 1, hi), hi, closest_so_far) else: # Search left return helper(arr, target, lo, max(mid - 1, lo), closest_so_far) if len(arr) == 0: return -1 return helper(arr, target, 0, len(arr) - 1, arr[0]) arr = [0, 10, 14, 27, 28, 30, 47] attempt = closest_value(arr, 26) print(attempt, arr[attempt]) assert attempt == 3 attempt = closest_value(arr, 29) print(attempt, arr[attempt]) assert attempt in (4, 5) def closest_values(arr, target): def left_helper(arr, target, abs_diff, lo, hi): # Base case if lo == hi: diff = arr[lo] - target if abs(diff) == abs_diff: return lo else: return lo + 1 # General case mid = ((hi - lo) >> 1) + lo diff = arr[mid] - target if diff < 0 and abs(diff) >abs_diff: # Search right return left_helper(arr, target, abs_diff, min(mid + 1, hi), hi) elif abs(diff) == abs_diff: # Search left return left_helper(arr, target, abs_diff, lo, max(mid - 1, lo)) else: # Search left return left_helper(arr, target, abs_diff, lo, max(mid - 1, lo)) def right_helper(arr, target, abs_diff, lo, hi): # Base case if lo == hi: diff = arr[lo] - target if abs(diff) == abs_diff: return lo else: return lo - 1 # General case mid = ((hi - lo) >> 1) + lo diff = arr[mid] - target if diff < 0 and abs(diff) >abs_diff: # Search right return right_helper(arr, target, abs_diff, min(mid + 1, hi), hi) elif abs(diff) == abs_diff: # Search right return right_helper(arr, target, abs_diff, min(mid + 1, hi), hi) else: # Search left return right_helper(arr, target, abs_diff, lo, max(mid - 1, lo)) a_closest_value = closest_value(arr, target) if a_closest_value == -1: return -1, -1 n = len(arr) abs_diff = abs(arr[a_closest_value] - target) left = left_helper(arr, target, abs_diff, 0, a_closest_value) right = right_helper(arr, target, abs_diff, a_closest_value, n - 1) return left, right arr = [0, 10, 14, 27, 27, 29, 30] attempt = closest_values(arr, 28) print(attempt, arr[attempt[0] : attempt[1] + 1]) assert attempt == (3, 5) attempt = closest_values(arr, 27) print(attempt, arr[attempt[0] : attempt[1] + 1]) assert attempt == (3, 4) How can I get a first element from a sorted list?
I used Collections.sort(playersList); to sort a List . So, I think playersList is sorted now. But how can I get the first element of the list? playersList[0] does not work.
8 Answers 8
Java has limited operator polymorphism. So you use the get() method on List objects, not the array index operator ( [] )
You have to access lists a little differently than arrays in Java. See the javadocs for the List interface for more information.
However if you want to find the smallest element in playersList , you shouldn’t sort it and then get the first element. This runs very slowly compared to just searching once through the list to find the smallest element.
int smallestIndex = 0; for (int i = 1; i < playersList.size(); i++) < if (playersList.get(i) < playersList.get(smallestIndex)) smallestIndex = i; >playersList.get(smallestIndex); The above code will find the smallest element in O(n) instead of O(n log n) time.
I wander why such a basic operation should be programed. Why Java does not provide a function which returns just a minimal value from array?
That depends on what type your list is, for ArrayList use:
if you like the array approach:
bad advice. LinkedList implements the List interface, no need to use a special method (and I’d be amazed of there was any performance difference between the two). And calling toArray() is wasteful—you might be allocating the list into a new array for no reason!
@Kip, strange remark; the LinkedList class does not implement the first and last methods out of spite. If you have a good reason to use a LinkedList, you should not refrain from using its methods just because they are not in the List interface. The array example can be usefull if the list itself is not needed after sorting, and closest to what OP asked. Without knowing the context of the source code in question you cannot determine the validity of the advice.
why would it matter whether or not you need the list after sorting? in either case (or even if the list is never sorted) calling toArray() just to get the first element (may) needlessly create an entire array.
@Kip, you are right in that retrieving an array just for the first element is ot a good idea if you don not plan to use the array. The question asked for how to get the first element from a list and mentioned an array context. I merely gave alternatives touching those concepts. It is up to the programmer who knows his source to make a choice from these alternatives.
Using Java 8 streams, you can turn your list into a stream and get the first item in a list using the .findFirst() method.
List stringsList = Arrays.asList("zordon", "alpha", "tommy"); Optional optional = stringsList.stream().findFirst(); optional.get(); // "zordon" The .findFirst() method will return an Optional that may or may not contain a string value (it may not contain a value if the stringsList is empty).
Then to unwrap the item from the Optional use the .get() method.
Here’s an interesting presentation by Mark Reinhold about Java 7
It looks like parleys site is currently down, try later 🙁
If your collection is not a List (and thus you can’t use get(int index) ), then you can use the iterator:
Iterator iter = collection.iterator(); if (iter.hasNext())
If you just want to get the minimum of a list, instead of sorting it and then getting the first element ( O(N log N) ), you can use do it in linear time using min :
That looks gnarly at first, but looking at your previous questions, you have a List . In short: min works on it.
For the long answer: all that super and extends stuff in the generic type constraints is what Josh Bloch calls the PECS principle (usually presented next to a picture of Arnold — I’M NOT KIDDING!)
Producer Extends, Consumer Super
It essentially makes generics more powerful, since the constraints are more flexible while still preserving type safety (see: what is the difference between ‘super’ and ‘extends’ in Java Generics)
Efficiently find an element in multiple sorted lists?
Problem Statement:- I was ask this interview question recently.. I was able to come up with the below code only which runs in O(k log n)- Given k
private List> dataInput; public SearchItem(final List> inputs) < dataInput = new ArrayList>(); for (List input : inputs) < dataInput.add(new ArrayList(input)); > > public List getItem(final Integer x) < Listoutputs = new ArrayList(); for (List data : dataInput) < int i = Collections.binarySearch(data, x); // binary searching the item if (i < 0) i = -(i + 1); outputs.add(i == data.size() ? null : data.get(i)); >return outputs; > public static void main(String[] args) < List> lists = new ArrayList>(); List list1 = new ArrayList(Arrays.asList(3, 4, 6)); List list2 = new ArrayList(Arrays.asList(1, 2, 3)); List list3 = new ArrayList(Arrays.asList(2, 3, 6)); List list4 = new ArrayList(Arrays.asList(1, 2, 3)); List list5 = new ArrayList(Arrays.asList(4, 8, 13)); lists.add(list1); lists.add(list2); lists.add(list3); lists.add(list4); lists.add(list5); SearchItem search = new SearchItem(lists); System.out.println(dataInput); List dataOuput = search.getItem(5); System.out.println(dataOuput); > Whatever output I am seeing with my above code approach should come with the new approach as well which should work in O(k + log n) . Is this possible to achieve? Can anyone provide an example how would this work basis on my example?
Maybe merging the lists together as a pre-processing step, and then doing a binary search on the merged list?
Whatever approach I am doing currently in the code is called the iterated search query I guess? Not sure..
@ksun Won’t work. Merging is O(kn), but then searching is O(kn log kn), which is more than the given bound.