Matt C (cr4k) wrote in algorithms,

Finding the nearest in a sorted set of int to a given int

Hi guys,

I'm in the middle of writing a connector to some accounting software and I've been implementing a lazy loading list of proxies because I'm dealing with huge lists of items which load slowly (even the item id s load slowly).

That's not important to the question I am asking though, basically, I want an algorithm which finds either the given search int in my sorted set (of indexes) or the nearest int contained in the list (it doesn't matter, but we can say that the algorithm has a preference for lower numbers if 2 values are equally near)

The essence of the problem is outlined here:


import java.util.TreeSet;

public class Search {
static TreeSet sorted = new TreeSet();

public static void main(String...args){

sorted.add(1);
sorted.add(3);
sorted.add(5);
sorted.add(7);
sorted.add(10);

findNearest(2); // return 1
findNearest(8); // return 7
findNearest(10); // return 10
}

private static Integer findNearest(Integer search) {
return null; //TODO halp pls!
}
}


Thanks for any advice in advance!
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 14 comments

cr4k

December 5 2009, 14:42:36 UTC 4 years ago

It's strange how it always seems to help to explain the problem you are having...


private static Integer findNearest(Integer search) {
if(sorted.isEmpty())
return 0;

if(sorted.contains(search))
return search;

Integer higher = sorted.higher(search);
int higherDiff = absoluteDifference(higher, search);


Integer lower = sorted.lower(search);
int lowerDiff = absoluteDifference(lower, search);

if(lowerDiff > higherDiff)
return higher;

return lower;
}

private static int absoluteDifference(Integer a, Integer b) {
return Math.abs(a - b);
}

dair_targ_one

December 5 2009, 15:20:29 UTC 4 years ago

If you're need only implementation then java.util.Collections#binarySearch(..) method could help.
Otherwise (if you're really need implementation details) you could use plain binary search. It seems to be exactly what you need.

cr4k

December 5 2009, 15:27:49 UTC 4 years ago

binary search doesnt give me back the element nearest in value to the search key, it gives back the the index of the search key, if it is contained in the list; otherwise, the index of the insertion point.

lightning_rose

December 5 2009, 16:22:44 UTC 4 years ago


If your list is an array, then the index or the index plus or minus one will give you the element that is closest to the search key. An algorithm based on this will certainly be faster than searching the array twice.

cr4k

December 5 2009, 16:32:43 UTC 4 years ago

The real list is an unindexed list ordered by id on the other side of a dcom connection (which takes 10s of millisecs to respond). I need to find the nearest loaded index (and then id) to the element i am searching for so that i can move up or down to the correct item in the real list (the set in my example represents all of the indexes of elements which have already been loaded). For the purposes of my connector, it is ok to assume that the real list is read only.

lightning_rose

December 5 2009, 17:14:21 UTC 4 years ago


I'll assume it's not an array, then. :) (I don't do java)

cr4k

December 5 2009, 18:56:10 UTC 4 years ago

the real list can't be accessed by index so it couldn't be called an array (It's also not in Java, hence the dcom connection)

dair_targ_one

December 5 2009, 17:31:17 UTC 4 years ago

And what's the problem to get then element by its index? Index of insertion point is the index where the new element could be inserted so the list will remains sorted. So the two adjusted elements will be most nearest to the searched element of the whole list. Then you should only chose which one of them shoud be picked up. Something like:
 T getNearestElement(List list, T element) {
  int index = Collections.binarySearch(list, element);
  if (index > 0) {
    return list.get(index);
  } else {
    T prev = list.get(-index);
    T next = list.get(index);
    if (distance(prev, element) < distance(next, element)) {
      return prev;
    } else {
      return next;
    }
  }
}

The performance problem could appear only if you're used linked lists. But in that case, i think, every other algorythm will have O(N) time where N is list size.

dair_targ_one

December 5 2009, 17:33:17 UTC 4 years ago

UPD: About performance problem -- this problem exists in all lists where you hasn't random quick access.

cr4k

December 5 2009, 18:53:11 UTC 4 years ago

cool, I think your algorithm calls binary search half as much as mine, thanks

sidoitid77

December 5 2009, 17:36:22 UTC 4 years ago

mate, it seems to be easy for me..


private static Integer findNearest(Integer search) {
if(sorted.isEmpty())
return 0;

if(sorted.contains(search))
return search;

int higherDiff = Integer.MAX_VALUE;
Integer higher = sorted.tailSet(search).first();
if (higher!=null) higherDiff = absoluteDifference(higher, search);

int lowerDiff = Integer.MAX_VALUE;
Integer lower = sorted.headSet(search).last();
if (lower!=null) lowerDiff = absoluteDifference(lower, search);

if(lowerDiff > higherDiff)
return higher;

return lower;
}



I didn't try to compile it. So you need to debug.

sidoitid77

December 5 2009, 17:41:18 UTC 4 years ago

of course, I assume that sorted is an instance of TreeSet

sidoitid77

December 5 2009, 17:54:29 UTC 4 years ago

This code should be modified slightly. I've read that if tailSet or headSet is empty, then calling first() or last() will result in NoSuchElementException.

SO try to use this one:


private static Integer findNearest(Integer search) {
if(sorted.isEmpty())
return null;

if(sorted.contains(search))
return search;

int higherDiff = Integer.MAX_VALUE;
Integer higher = null;
SortedSet tailSet = sorted.tailSet(search);
if (!tailSet.isEmpty()) {
higher = tailSet.first();
higherDiff = absoluteDifference(higher, search);
}

int lowerDiff = Integer.MAX_VALUE;
Integer lower = null;
SortedSet headSet = sorted.headSet(search);
if (!headSet.isEmpty()) {
lower = headSet.last();
lowerDiff = absoluteDifference(lower, search);
}

if(lowerDiff > higherDiff)
return higher;

return lower;
}

czarandy

December 6 2009, 01:41:45 UTC 4 years ago

Standard binary search + 1 minor change at the end for the return value.