Блог пользователя jaswanthi

upper_bound in Java for binary search
Автор jaswanthi, история, 9 лет назад, По-английски

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

PS: I did google this

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Java has Arrays.binary_search() static method instead.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://scod.ir/Yit

→ Ответить