Win a copy of Svelte and Sapper in Action this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Bear Bibeault
  • Junilu Lacar
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • salvin francis
  • Frits Walraven
Bartenders:
  • Scott Selikoff
  • Piet Souris
  • Carey Brown

Doubt in Array's binarySearch question

 
Ranch Hand
Posts: 125
Scala Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This question is from K&B Questions book for scjp 6.




Explanation:


How is the answer -1?
I know the forumla is: (-(insertion point)-1), but if no sorting instance is passed as an argument in binarySearch method, what is the criteria for finding out the answer? I mean what if the answer choices were as follows:
a. -1
b. -2
c. -3
How would I tell whether its -1 or -2 or -3?
 
Bartender
Posts: 4067
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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, t-ride, 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 t-ride,
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
 
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.)
 
Sidharth Khattri
Ranch Hand
Posts: 125
Scala Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.)



hi Anayonkar,

Using this:

When searching for vail, the result is 5
and when searching for t-ride, the result is 1
So I'm pretty sure the answer is not always -1
 
Sidharth Khattri
Ranch Hand
Posts: 125
Scala Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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, t-ride, 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 t-ride,
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



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 t-ride, the result is 1
 
Anayonkar Shivalkar
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Sidharth Khattri wrote:When searching for vail, the result is 5
and when searching for t-ride, the result is 1
So I'm pretty sure the answer is not always -1


Exactly. What my point is: since you are using one algorithm to sort the list and another algorithm to perform search, you'll not get correct results (e.g. t-ride is not at position 1 and vail is not at position 5).
However, it is unlikely that you'll get -2 or -3 (I guess).
 
Piet Souris
Bartender
Posts: 4067
156
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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 t-ride, 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 item-to-be-searched-for
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 N-1 (i.e. array has N items), then try item number (0 + N-1) / 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, t-ride, dillon, aspen, in that sequence.

Now in this array we do the BinarySearch. It picks item 1, being t-ride. (item 0 is vail). It compares t-ride 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 t-ride, well, it starts with comparing this with t-ride (just pure luck, that is). It finds t-ride at index 1, and so
it returns 1.

Greetings,
Piet
 
author
Posts: 23883
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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 t-ride, the result is 1



Sidharth has a good point. We kinda know the answer because we know how the binary search algorithm works. We know that it kinda cuts the list in half, and recursively does it again based on the result of the middle item that is tested.

However, I don't think the JavaDocs mentions this gory details. It merely says that the list must be sorted (in the same fashion as the search comparator). Otherwise, it makes no guarantees of correctness or incorrectness. So, arguably, the test question is not correct. It may consistently return -1, but it is not documented to do so.

Henry
 
Ranch Hand
Posts: 68
MyEclipse IDE PHP Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Great explanation Piet, I think there is an explanation error (expl. posted in the question): there is no inner class.
 
Sidharth Khattri
Ranch Hand
Posts: 125
Scala Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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 t-ride, 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 item-to-be-searched-for
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 N-1 (i.e. array has N items), then try item number (0 + N-1) / 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, t-ride, dillon, aspen, in that sequence.

Now in this array we do the BinarySearch. It picks item 1, being t-ride. (item 0 is vail). It compares t-ride 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 t-ride, well, it starts with comparing this with t-ride (just pure luck, that is). It finds t-ride at index 1, and so
it returns 1.

Greetings,
Piet



Thanks for your flawless explanation. Sorry for the typo, searching for vail returns -5
 
No. No. No. No. Changed my mind. Wanna come down. To see this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic