aspose file tools*
The moose likes Beginning Java and the fly likes binary search in collections Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "binary search in collections" Watch "binary search in collections" New topic
Author

binary search in collections

veena bijur
Ranch Hand

Joined: May 16, 2011
Posts: 67


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
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
veena bijur wrote: . . .
Have you read the documentation for binarySearch and what happens if the element sought is not found?
veena bijur
Ranch Hand

Joined: May 16, 2011
Posts: 67

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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: May 16, 2011
Posts: 67

i did not get the below line

(-(insertion point) - 1)
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18988
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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
Sheriff

Joined: Sep 28, 2004
Posts: 18988
    
  40

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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: binary search in collections