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 ;-)