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!

cr4kDecember 5 2009, 14:42:36 UTC 5 years ago

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_oneDecember 5 2009, 15:20:29 UTC 5 years ago

`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.cr4kDecember 5 2009, 15:27:49 UTC 5 years ago

elementnearest in value to the search key, it gives back the theindexof the search key, if it is contained in the list; otherwise, theindexof the insertion point.lightning_roseDecember 5 2009, 16:22:44 UTC 5 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.

cr4kDecember 5 2009, 16:32:43 UTC 5 years ago

lightning_roseDecember 5 2009, 17:14:21 UTC 5 years ago

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

cr4kDecember 5 2009, 18:56:10 UTC 5 years ago

dair_targ_oneDecember 5 2009, 17:31:17 UTC 5 years ago

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_oneDecember 5 2009, 17:33:17 UTC 5 years ago

cr4kDecember 5 2009, 18:53:11 UTC 5 years ago

sidoitid77December 5 2009, 17:36:22 UTC 5 years ago

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.

sidoitid77December 5 2009, 17:41:18 UTC 5 years ago

`sorted`

is an instance of`TreeSet`

sidoitid77December 5 2009, 17:54:29 UTC 5 years ago

`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;

}

czarandyDecember 6 2009, 01:41:45 UTC 5 years ago

notthebuddhawrote inalgorithms: ←Big-O for other parameters?dangiankitwrote inalgorithms: →1st Call for Papers: SIGAI Workshop on Emerging Research Trends in AI (ERTAI-2010)