OCPJP 6  96%
Currently working on Scala at Knoldus Software
I hate signatures!
Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
Anayonkar Shivalkar wrote:Hi Sidharth,
As explanation of the answer mentions: when an array is sorted by logic 'x' then the logic 'x' must be passed to binary search method. If no logic is passed, then binary search method will assume that the array is sorted by default logic (and, if array is not actually sorted by default logic, then binary search may give wrong result).
Regarding return value  as per documentation, binary search method returns 1 if the object is not found (as per default/provided sorting logic). I don't think binary search will return any negative value other than 1 (i.e. 2 or 3 etc.)
OCPJP 6  96%
Currently working on Scala at Knoldus Software
Piet Souris wrote:hi Sidharth,
again one of those nasty exam questions.
class MySort sorts the array in descending order. So, after the sort,
the array is : vail, tride, dillon, aspen.
Then it is asked to do the binary search for "dillon". It starts searching,
probably from position (max_index + first_index)/2 = 1.
So it starts looking at the bottom half, i.e. in vail and tride,
and it won't find dillon. It would have inserted this word in position 0, giving
a return value of 1, according to your formula.
Greetz,
Piet
OCPJP 6  96%
Currently working on Scala at Knoldus Software
Sidharth Khattri wrote:When searching for vail, the result is 5
and when searching for tride, the result is 1
So I'm pretty sure the answer is not always 1
Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
Sidharth Khattri wrote:Hi Piet,
I've never seen that formula anywhere, can you please elaborate what is the bottom half and the other half?
And how does this happen?
Using this:
When searching for vail, the result is 5
and when searching for tride, the result is 1
I hate signatures!
Sidharth Khattri wrote:
Hi Piet,
I've never seen that formula anywhere, can you please elaborate what is the bottom half and the other half?
And how does this happen?
Using this:
When searching for vail, the result is 5
and when searching for tride, the result is 1
hth
Piet Souris wrote:
Sidharth Khattri wrote:Hi Piet,
I've never seen that formula anywhere, can you please elaborate what is the bottom half and the other half?
And how does this happen?
Using this:
When searching for vail, the result is 5
and when searching for tride, the result is 1
When using a binary search method to search for some item in an array,
what you do is:
1) assume that the array is sorted, in ascending order
2) now, try the middle item of the array and look whether it is equal to the itemtobesearchedfor
3) if you are lucky, you find equality and you're done
4) if not, then, since the array is assumed to be sorted, determine whether the item must be in the first half of
the array, or in de second half.
5) so you now know in which half the item must be in, and with this reduced array you go back to step 2.
Well, matbe you knew all of this already, but here's my formula: how would you pick the middle item of an array?
One possibility is: if the arraylength is N, then pick item(N / 2).
Another is: is the first index = 0 and the last index is N1 (i.e. array has N items), then try item number (0 + N1) / 2
or (and that I was referring to) (first index + last index) / 2.
In the given array, containing 4 elements, I guess the binarySearch picks item 1 as its first try ( i.e. (0 + 3) / 2 = 1).
As I said, the trick of this question is that you have done a sort on the array that sorts descending.
So, the array after sorting is: vail, tride, dillon, aspen, in that sequence.
Now in this array we do the BinarySearch. It picks item 1, being tride. (item 0 is vail). It compares tride to dillon, comcludes
that dillon is smaller, and so the BS thinkis it must be looking in the first (or botrtom) half, which is in this case only item
vail. BS assumes the array to be sorted in ascending order; that we have sorted it in descending order, well, that's why it
is wrong to use a plain BS here. We should have told the BS that the sorting was different, by giving it the sorting
that we have done. See the API of Arrays.BinarySearch for the full story.
Anyway, BS being completely wrong here, but doesn't know this, it has not found dillon, and it would have inserted dillon
at position 0, sice dillin comes before vail. In the API you see that the return value is exactly the formula that you mentioned, i.e.: 0  1 = 1.
This is crucial. if the BS would have started at index 2, had it used the other method to determine the starting point, it would have started with dillon,
and so it would have found dillon, and the return value would have been 2.
Now I must admit to not knowing which of the two starting positions the BS uses. I don't know if that is specified somewhere, so frankly,
without trying I would not have known whether the correct answer is 1 or +2. It's a nasty question, therefor.
Then, you say that a search for vail gives an outcome of 5. Are you sure it is not 5? If it is 5, then I cannot explain this, since I do not understand. However,
it will not find vail in our sorted array, for the same reason that it doesn't find dllon. It would have inserted vail at position 4 (right after aspen), and therefore the
retrurn value is: 4  1 = 5.
If you search for tride, well, it starts with comparing this with tride (just pure luck, that is). It finds tride at index 1, and so
it returns 1.
Greetings,
Piet
OCPJP 6  96%
Currently working on Scala at Knoldus Software
No. No. No. No. Changed my mind. Wanna come down. To see this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/ThreadBoostfeature
