Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# BinarySearch() Question

Tayitu Betule
Ranch Hand
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
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 ;-)

Tayitu Betule
Ranch Hand
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.