2

I have a TreeSet<Integer> set = new TreeSet<>();

I fill the set with some Values: set.add(i); // i=1,5,7,44,9,7 Since it is a sorted Set, I should be able to have the set as follows. 1 - 5 - 7 - 9 - 44

now I want to know the position of 9 in the set, which is 3 in this case.

1) I could do a linar search, iterating over the set, increasing a value, it the current element is not equal to the element Im searching for,

2) I could do a Binery Recursive search, determining the length, splitting the set in two, getting the last element of the first subset, determining then, in which subset I proceed the search, and so on.

Is there a cheaper method to search the index of a value in the set?

Josh Crozier
  • 233,099
  • 56
  • 391
  • 304
Joel
  • 1,725
  • 3
  • 16
  • 34
  • 3
    Hey Joel, there was already a question asked on this topic... please refer this http://stackoverflow.com/questions/7911621/how-to-find-the-index-of-an-element-in-a-treeset. This will help you to get the right solution – Katie Aug 20 '15 at 16:11
  • 1
    A binary search is **O(log n)** while a linear search is **O(n)**. – dsh Aug 20 '15 at 16:11
  • 2
    @dsh that makes no sense. O(n/2) is the same thing as O(n). A binary search is O(log n) – JB Nizet Aug 20 '15 at 16:14
  • The base of that log is 2, maybe that's the source of confusion @dsh? – yshavit Aug 20 '15 at 16:15
  • @JBNizet my mistake; I thought I should look it up instead of trying to recall – dsh Aug 20 '15 at 16:16
  • 1
    TreeSet doesn't have indecies but it does a O(log N) search already. You don't need to do anything, it is written for you. – Peter Lawrey Aug 20 '15 at 16:20

0 Answers0