• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

binary search in collections

 
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


in the above list, element "B" not there so i want to display element not found, how to do that?

in the above code if element doesnt exist it displays run-time error, how to catch that error.

Please help
 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

veena bijur wrote:
in the above list, element "B" not there so i want to display element not found, how to do that?



What do the docs tell you about how binarySearch() works?

in the above code if element doesnt exist it displays run-time error, how to catch that error.



You shouldn't catch RuntimeExceptions. You should fix your code so they don't happen. In this case, you should not call get() for an index that does not exist.
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

veena bijur wrote: . . .

Have you read the documentation for binarySearch and what happens if the element sought is not found?
 
veena bijur
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Hi,

Campbell
Have read the documentation but did not get it

if element is found the index of the search key, is obtained( i got that and have implemented in the above code)
else: (-(insertion point) - 1). could you please explain the else part.


Thanks
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

veena bijur wrote:
else: (-(insertion point) - 1). could you please explain the else part.



There are only a few parts to it.


else
-
insertion point
(and this one is defined in the doc right after the above summary that you quoted)
-
1


Which of those do you not understand?

And also, the last sentence of the "Returns:" part tells you everything you need to know to interpret the result. So I gotta admit, I'm confused as to what you're having trouble with.
 
veena bijur
Ranch Hand
Posts: 67
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

i did not get the below line

(-(insertion point) - 1)
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

veena bijur wrote:
i did not get the below line

(-(insertion point) - 1)



Yes. I know that. Here are the parts of that line. Which of them do you not understand?


else
-
insertion point
-
1


Do you know what "else" means?
Do you know what the - sign means in a mathematical contect?
Do you know what "insertion point" means? (It's defined in the javadoc right after that line that you qutoed.)
Do you know what 1 means?

And note that you don't even need to understand that line. The last sentence of the "Returns:" section of the javadoc tells you all you need to know to interpret the result when it's not found.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you tried just calling the binarySearch() method for various values that are present and not present, and looking at the results? If you do that, and re-read the docs, it should be blatantly obvious what's going on.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

veena bijur wrote:
i did not get the below line

(-(insertion point) - 1)



The "insertion point" is the location where the item has to be inserted ... for example, if the collection contains 2 45 89 103 222, and you want to see if 78 is on the list, then the insertion point is between the 2nd and 3rd element. As for the value, the documentation defines that as the "index of the first element greater", and since the index of the 3rd element is two the insertion point is two, and the value returned is -3.

Regardless, in your case, it is moot. You don't care about the insertion point, you just want to know if the item is on the list. So, you just care to know if the value returned is negative or not.

Henry

 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:Have you tried just calling the binarySearch() method for various values that are present and not present, and looking at the results? If you do that, and re-read the docs, it should be blatantly obvious what's going on.



For example:


 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeff Verdegan wrote:Have you tried just calling the binarySearch() method for various values that are present and not present, and looking at the results? If you do that, and re-read the docs, it should be blatantly obvious what's going on.



Jeff,

Perhaps the OP is not a native english speaker? The documentation may sound straightforward to you and I, but I am sure that there are idioms (or experience related stuff) that makes it difficult to understand.


Regardless, you do have point. In terms of difficulty, there will likely be problems which arise during one's career that is orders of magnitude more difficult -- and the OP should get into a habit of just experimenting with stuff.

Henry
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Henry Wong wrote:

Jeff Verdegan wrote:Have you tried just calling the binarySearch() method for various values that are present and not present, and looking at the results? If you do that, and re-read the docs, it should be blatantly obvious what's going on.



Jeff,

Perhaps the OP is not a native english speaker? The documentation may sound straightforward to you and I, but I am sure that there are idioms (or experience related stuff) that makes it difficult to understand.



Absolutely. And that's why I'm asking him to look at the pieces of that one phrase he's having trouble with and tell us what in particular he's not getting. And the above comment about it being blatantly obvious if he combines observation of the behavior with reading the docs isn't meant to be condescending or insulting. Rather, I meant that I'm hopeful that whatever confusion he has will evaporate when he sees the very straightforward pattern that will appear.

And of course, using observation and documentation together is a good habit to get into for the general case. I am a native English speaker and I sometimes find documentation hard to understand or just too sparse to fully describe the behavior. So I take an educated guess as to what I think it might mean and run some tests to confirm my theory, or show me where it needs refining.

Actually, that brings up another point.

@OP: Even if you don't understand some piece of the docs, you can make an educated guess as to what might be happening. For instance, in this case, you said you understand the part that says that if the element is found, it will return the index where it found it, right? So now if we're still confused about what it returns if it doesn't find it, we stop and think: If it's found, the result is the index where it is in the array. An array can have indices from 0 up to (in theory) Integer.MAX_VALUE. That means that 0 and all the positive ints are taken for the "found" case. There's no way it can return 0 or a positive int if it didn't find the value, because that would clash with a potential "found" result. So, if the method returns an int, and 0 and the positive ints are ruled out, what does that leave for when the value is not found?

I'm not trying to beat you up here. I'm just trying to nudge you toward combining what you got from the docs + your ability to think logically and use common sense + a habit of experimenting, so that when something new has you confused again in the future, you'll have the tools to work through it.
reply
    Bookmark Topic Watch Topic
  • New Topic