• 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

Question regarding binarySearch....

 
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Given a properly prepared String array containing five elements, which range of results could a
proper invocation of Arrays.binarySearch() produce?

A. 0 through 4
B. 0 through 5
C. -1 through 4
D. -1 through 5
E. -5 through 4
F. -5 through 5
G. -6 through 4
H. -6 through 5

And the answer is given as G. As per my understanding the binarysearch index would return -1 if the match is not found since 0 is also considered as a successful match. So for 0 it is -1, 1 it is -2 and so on until 4 it is -5. So as per my understanding the answer would be E. Isn't it? Please clarify.
 
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If the element used in binarySearch is greater than all elements in the array, it would have to be inserted at position 5. Therefore binarySearch returns -(5) - 1 = -6 in this case.
[ July 24, 2008: Message edited by: Ralph Jaus ]
 
Ranch Hand
Posts: 141
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Page 556/557 of K&B 5 Book's


Regarding binarySearch


Unsuccessful searches return an int index that represents the insertion point.
The insertion point is the place in the collection/array where the element
would be inserted to keep the collection/array properly sorted. Because posi-
We�ve talked a lot about sorting by natural order and using Comparators
to sort. The last rule you�ll need to burn in is that, whenever you want to sort an array
or a collection, the elements inside must all be mutually comparable. In other words, if you
have an Object[] and you put Cat and Dog objects into it, you won�t be able to sort
it. In general, objects of different types should be considered NOT mutually comparable,
unless specifically stated otherwise.
tive 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 (-(insertion point) -1). For
instance, if the insertion point of a search is at element 2, the actual insertion
point returned will be -3
.


[ July 24, 2008: Message edited by: Raphael Rabadan ]
 
Justin Smith
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Ralph and Raphael for your reply... But this is where i am getting stuck.

"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 (-(insertion point) -1). Forinstance, if the insertion point of a search is at element 2, the actual insertion point returned will be -3."

So the insertion point for the 5th element (4th in index) is going to be
-5 right, how did we get to the -6, is that means say i have an array of 10 elements (0 to 9), the values would be from -11 through 9, is that the answer for the question then.....
 
Ralph Jaus
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Given a = {0,1,2,3,4}. Because the array doesn't contain 5, Arrays.binarySearch(a,5) looks at what position the 5 is to be inserted to keep the array sorted. And that's the position with index 5. Therefore the result is -(5) -1 = -6.
[ July 24, 2008: Message edited by: Ralph Jaus ]
 
Justin Smith
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Ralph now i got the point So if the size of array is N the binarysearch will go through from

-(N+1) through (N-1)

Thanks again for the help

 
Raphael Rabadan
Ranch Hand
Posts: 141
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Try this code:
 
Ralph Jaus
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Justin, you're right.

By the way, the satements

No insert Point --> -1
At 0 --> -2
At 1 --> -3
At 2 --> -4
At 3 --> -5

are wrong. -1 is returned, if the the element used in binarySearch is less than the smallest element in the array (that is, it has to be inserted at position 0 to keep the array sorted). Let a = {0,2,4,6,8}. Than Arrays.binarySearch(a,1) would return -2, because 1 has to be inserted at index position 1 to keep the array sorted. And so on.

-----------------------------------------

SCJP 1.5 (98%)
 
Ralph Jaus
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oh, I see, Raphael has removed his wrong statements.
 
Raphael Rabadan
Ranch Hand
Posts: 141
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Ralph Jaus:
Oh, I see, Raphael has removed his wrong statements.



Yeah, to not confuse anyone :-)
 
Justin Smith
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Ralph,

One more personal question, i saw the fantabulous score of yours (98%) and would like to know the secret behind the success. If you could share your preparation steps and notes that would be great.
 
Ralph Jaus
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Preparation&experiences
 
Justin Smith
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Ralph once again!!! But this time though for your prepartion tips......
reply
    Bookmark Topic Watch Topic
  • New Topic