# Question regarding binarySearch....

Justin Smith
Greenhorn
Posts: 19
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.

Ralph Jaus
Ranch Hand
Posts: 342
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
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
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
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
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

Ranch Hand
Posts: 141
Try this code:

Ralph Jaus
Ranch Hand
Posts: 342
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
Oh, I see, Raphael has removed his wrong statements.

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

Yeah, to not confuse anyone :-)

Justin Smith
Greenhorn
Posts: 19
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
Preparation&experiences

Justin Smith
Greenhorn
Posts: 19
Thanks Ralph once again!!! But this time though for your prepartion tips......