aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Invocation of Arrays.binarySearch() Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Invocation of Arrays.binarySearch()" Watch "Invocation of Arrays.binarySearch()" New topic
Author

Invocation of Arrays.binarySearch()

agilemanoj kumar
Ranch Hand

Joined: Mar 07, 2008
Posts: 70


The above problem is taken from K&B, Generics and Collections chapter, Q.9

Please explain me the answer...
[ May 09, 2008: Message edited by: agilemanoj kumar ]

Manoj Kumar
Stevi Deter
Ranch Hand

Joined: Mar 22, 2008
Posts: 265

Agilemanoj,

What do you think the answer is, and why?

If you're wrong, we'll help guide you to the right answer.


There will always be people who are ahead of the curve, and people who are behind the curve. But knowledge moves the curve. --Bill James
agilemanoj kumar
Ranch Hand

Joined: Mar 07, 2008
Posts: 70
I think, the answer should be F. Means, range should be -5 through 5.
There are 5 elements and to search an element using binarysearch, we generally use the range which is double of that array size plus 1.
So, here in the current scenario, for 5 elements, Range should contain 11 elements. And from my point of view, range should be -5 through 5.
-5 -4 -3 -2 -1 0 1 2 3 4 5.

Where am I wrong ??
Stevi Deter
Ranch Hand

Joined: Mar 22, 2008
Posts: 265

Let's review the API to see what the return value will be:


index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.


So, we know that it can only be >= 0 if the element is found in the list. If we have five elements in the array, then what is the maximum index we can return?

Now, we also see that the return if the element is not in the array is (-(insertion point) -1)

So, what will be returned if the key that's searched on would be inserted after the last element in the array? Wouldn't that be (-(array.length)-1)? What's that value for the described array?

This is an excellent example of why it really pays to just code code code to understand the question. Write a quick program that creates the array of five strings, and check the return values for each member of the array, and then search on values that would be inserted at different places in the array to see what the real results are.
[ May 09, 2008: Message edited by: Stevi Deter ]
Ram Manoj
Ranch Hand

Joined: Jan 12, 2008
Posts: 52
Is proper invocation of Arrays.binarySearch() mean


from the API
The array must be sorted into ascending order according to the natural ordering of its elements (as by Sort(Object[]), above) prior to making this call. If it is not sorted, the results are undefined.


or something else.
agilemanoj kumar
Ranch Hand

Joined: Mar 07, 2008
Posts: 70
got it... thank you so much
Stevi Deter
Ranch Hand

Joined: Mar 22, 2008
Posts: 265

Ram,

You are correct, in order to get the full range of results, you'll need to properly sort your array first. Otherwise, the undefined nature of the return results mean you may never see the full range.

Writing code to test both without sorting the array and then with will let you see the differences.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Invocation of Arrays.binarySearch()