• Post Reply Bookmark Topic Watch Topic
  • New Topic

generics doubt  RSS feed

 
anita dhar
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This question is from k&b from generics self test , i am not getting how this output will come can any one expalin me this
Given a prepared String array containing five elements , which range of results could a proper invocation of Arrays.binarySearch() produduce

o/p is -6 through 4
 
Deepak Jain
Ranch Hand
Posts: 637
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
Since the given string array has 5 elements, the method will return o-4 for successful search which are the possible indexes into the array and for uncessecufful search it would return the insertion point and for an an array with 5 elements the possible insertion points it can return are -1,-2,-3,-4,-5 and hence the method can return 0,1,2,3,4, -1,-2,-3,-4,-5 and hence the answer should be from -5 to 4.

For example the given string array has String [12,13,14,15,16] so a invocation Arrays.binarySearch(str,12) will result 0 because 12 is present @ index 0 and in a similar way it can return 0 - 4 for all successful search. If the element to be searched is present in the array then the method would return the index of the element in the array or else it will return the insertion point. Since positive return values implies successful search a -ve value to indicate insertion point and when these values inverted and decremented would indicate the index at which the given element can be inserted into the array to maintain the sorting order. So if I would invoke Arrays.binarySearch(str, 10) the return value would be -1 which implies the element 10 can be inserted @ index 0 [ index = (-(insertion point) - 1)). Since this array has 5 elements possible insertion points can be -1,-2,-3,-4,-5

I dont understand why the answer G -6 to 4 is correct in the book.
Thanks
Deepak
 
anita dhar
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks i understand , then its o/p is given in the book is wrong
am i right
 
Manfred Klug
Ranch Hand
Posts: 377
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Deepak Jain:
and for an an array with 5 elements the possible insertion points it can return are -1,-2,-3,-4,-5 and hence the method can return 0,1,2,3,4, -1,-2,-3,-4,-5 and hence the answer should be from -5 to 4.
You have forgotten that one possible insertion point is after the last element. So the possible insertion points are 0, 1 ,2 ,3 ,4 and 5, which are translated to -1, -2, -3, -4, -5 and -6. Conclusion, the answer in the book is correct.
 
anita dhar
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i am in cofusion what is the exact o/p of this question
 
Manfred Klug
Ranch Hand
Posts: 377
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi aneea,

there is a very simple way to solve your doubt. Try it. Make an array of five int's (say new int[] {5,7,9,11,13}), and search for the numbers from 4 up to 14.
 
Deepak Jain
Ranch Hand
Posts: 637
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If the array has 5 elements the only possible indexes are 0,1,2,3 and 4. How can we have index 5? Aren't indexes support to start from 0 and in Java if the size of the array is 5 then the indexes can be from 0-4 only.
Could you please explain how can we have index number 5?
If we can have 5 then offcourse there is another possible insertion point
-6.
Thanks
Deepak
 
Manfred Klug
Ranch Hand
Posts: 377
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Deepak,

same suggestion as for aneea. Try it!
 
Deepak Jain
Ranch Hand
Posts: 637
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Manfred, binarySearch() can return -6 if the number to be searched is greater than the greatest number in the array. So for an array with 5 elements the possible values can be 0,1,2,3,4 and -1,-2,-3,-4,-5,-6. So 4 through -6 is correct answer.
 
Manoj Macwan
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Manfred,

Thanks for making us understand how the binarySearch can return -6 in the result.

I have one doubt regarding the same question:

As we discussed
-6 : Returned when Integer is greater than current MAX(Array Element) is being searched.
-4 : Returned when Integer is less than current MAX(Array Element)is being searched.
My Condition:
Integer[] str = {1,12,9,12,10};
Arrays.sort(str);
System.out.println(Arrays.binarySearch(str,11)); //Return -4
System.out.println(Arrays.binarySearch(str,13)); //Return -6

When can we receive -5 in the search?
 
kishore Kumar Sangam
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Dude,
The sorted array will appear something like thing

Data 1 9 10 12 12
Pos index 0 1 2 3 4

Search Index -1 -2 -3 -4 -5

You are searching for element 13 and you will get -6 always.In this scenario you can never get -5.

Change the data to get -5.

1 8 17 20 38 [Unique elements]
 
Manoj Macwan
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Kishor,
Thanks for reply.
 
Manoj Macwan
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Kishor,
Thanks for reply.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!