• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Invocation of Arrays.binarySearch()

 
agilemanoj kumar
Ranch Hand
Posts: 70
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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 ]
 
Stevi Deter
Ranch Hand
Posts: 265
Hibernate Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Agilemanoj,

What do you think the answer is, and why?

If you're wrong, we'll help guide you to the right answer.
 
agilemanoj kumar
Ranch Hand
Posts: 70
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 265
Hibernate Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 52
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 70
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
got it... thank you so much
 
Stevi Deter
Ranch Hand
Posts: 265
Hibernate Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic