Zzyzx's blog

By Zzyzx, 11 years ago, In English

Hello,

Just today I took part in a virtual contest and I came across a question in which I had to use the Java equivalent of C++'s lower_bound() which searches in a given range in a sorted array (of integers, say),for the first element which is not less than a given value.

For example, suppose we have array A[] = { 1, 2, 3, 5, 6 }. Now in C++, lower_bound(A, A+5, 4) returns the index of 5 because it is the first element in the given range( here the entire array ) which is not less than the given value ( which is 4).

If there is a Java equivalent of the above function that can be used in arrays, what is it? The last thing I want to do is hard code this function every time I need to use it.

Thanks in advance for any pointers!

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is's java.util.Arrays.binarySearch()
Docs

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

    Should've paid more attention to the return value part! Thank you!

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    There is some difference between this methods:

    If the array contains multiple elements with the specified value java does not guarantee which one will be found

    lower_bound finds first element in this case

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

      I think therefore, the best option is to write my own function. Doesn't take much time and safe to use. Am I right or wrong?

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Btw, thanks for pointing that out!