Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Arrays java.util collections class - binarySearch() method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Arrays java.util collections class - binarySearch() method " Watch "Arrays java.util collections class - binarySearch() method " New topic
Author

Arrays java.util collections class - binarySearch() method

Ted North
Ranch Hand

Joined: Jan 02, 2012
Posts: 192
    
    1

You who read me now: I am having great problems understanding binarySearch(). I have no idea how to predict the output from this method.
Below, one will find problem number 16 from the Chapter 7 self exam in the most excellent Sierra and Bates (2008) SCJP book.

The output should be: pen marble map key -1

I have no clue how the output is -1 for the binarySearch().



Sebanti Sanyal
Ranch Hand

Joined: Nov 07, 2011
Posts: 58

The comparator object that is used for sorting is not used in binary search. Hence the the key won't be found. Negative values indicate "key not found" in binary search. You will get the correct result with the following modification:


Ted North
Ranch Hand

Joined: Jan 02, 2012
Posts: 192
    
    1

Hello Sebanti,

I input your code like so:



This output gives: pen marble map key -1
2


Why is the output for new code 2?

Also when I put "marble" as the key in the binary search I receive positive integer, 1, as a result. When I put "map" or "key" in I receive the -1 output that still does not make any sense to me. I found that "pen" yields -5 as output...I am not sure if these results are consistent with each run though.

Thanks for the input though - crowd-source your problems,

Ted North
Sebanti Sanyal
Ranch Hand

Joined: Nov 07, 2011
Posts: 58

Your comparator does a reverse sorting. When you use the same for binary search (new code), you get the correct index in the sorted array. Here, the sorted order is "pen marble map key" and so the index of "map" is 2.
If the same Comparator is not used in both sorting and binary search, result is unpredictable. In this case, however, I expect binary search to give negative results. I also checked 'System.out.println(Arrays.binarySearch(s, "marble"));' prints 1,which is the correct index. But for all other keys, result is negative as I expected. I have no clues.
 
 
subject: Arrays java.util collections class - binarySearch() method