*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes BinarySearch() Question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "BinarySearch() Question" Watch "BinarySearch() Question" New topic
Author

BinarySearch() Question

Tayitu Betule
Ranch Hand

Joined: Dec 18, 2009
Posts: 39
Here is a question from K&B:

Given a properly prepared String array containing five elements, which range of results could a
proper invocation of Arrays.binarySearch() produce?

The answer is -6 through 4. Why not -1 through -6? If the search element should have been inserted at the beginning, then -1 or if it should have been at the end, then -6.
Please correct me if I'm wrong.

Thank you all.
Ulrich Vormbrock
Ranch Hand

Joined: Apr 15, 2010
Posts: 73
Hi Tayitu,

if you've got SCJP 6 (K&B book), please read again page 577:
Because positive return values and 0 indicate successful searches, the binarySearch() method uses negative numbers to indicate insertion points. Since 0 is a valid result for a successful search, the first available insertion point is -1. Therefore, the actual insertion point is represented as (-(insertionpoint-1).

To illustrate this, let's have a look at the following piece of code:

As you can see, the "highest" value from arr is "+5", standing at its correct position (index=4). Due to the fact that
a) it deals with a CORRECT position (hence: no increment necessary concerning insertion point) and
b) array indexes always start at 0 (and not at 1),

the index of such correct position can reach only 4 (and not 5) - or as a rule of thumb - the maximum index of an array (arr.length - 1).
Please take into account that we are talking about correct positions, as well.

Below please find the output of the program above:

element "1": should stand at index 0
element "2": correct position with index 2
element "3": should stand at index 4
element "4": should stand at index 4
element "5": correct position with index 4


Another question which comes into play is the following:
why are the elements "3" and "4" supposed to stand both at position (index) "4"?
In fact, index "4" is (correctly) occupied by element "5".

Hope it helps ... and hope you help me ;-)

SCJP 6 (88%), SCWCD (89%)
Tayitu Betule
Ranch Hand

Joined: Dec 18, 2009
Posts: 39
Hi Ulrich,

Thank you for taking the time to post the detailed explanation. I guess I was just thinking of only if the search was unsuccessful... which makes the range -1 to -6 but the successful search results in index range 0 to 4... so the range will be -6 through 4.

Thanks again and hope to help you sometime.

Good luck.
 
 
subject: BinarySearch() Question