• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

BinarySearch() Question

 
Ranch Hand
Posts: 39
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 73
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic