jaswanthi's blog

upper_bound in Java for binary search
By jaswanthi, history, 8 years ago, In English

I couldn't find upper_bound equivalent in java. Is there any alternative function that I can use ?

PS: I did google this

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can write your own upper_bound and lower_bound (It's not hard), and there is another alternative (using a TreeSet)

Here are some methods :

ceiling(E e) : Returns the least element in this set greater than or equal to the given element, or null if there is no such element.

floor(E e) : Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

headSet(E toElement) : Returns a view of the portion of this set whose elements are strictly less than toElement.

You can find the full documentation here : https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Java has Arrays.binary_search() static method instead.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it is not useful in that case. If there are more than one element present in the array it will return any index.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Create array of pairs (a[i], i). Then use binarySearch(new Pair(x, -1)) or binarySearch(new Pair(x, n))

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes it can be done in that way but using object array results in taking far more time in sorting than primitive array.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://scod.ir/Yit

→ Reply