Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Binary Search

 
Duran Harris
Ranch Hand
Posts: 608
Eclipse IDE Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi...

from the K&B Master Exam there is a question along the lines of:

'If you have a properly prepared list of five elements,what range of results could the binarySearch() method return?'

The answer:-6 to 4(I think)

Now I know that binarySearch,if the item is not found will return the appropriate index to maintain the sort order by inverting and decr4ementing the appropriate index.

So.. a list of 5 elements:

list[0] =>returns -1 if the item is not found and should be placed here
list[1]=>returns -2 if the item is not found and should be placed here
list[2]=>returns -3 if the item is not found and should be placed here
list[3]=>returns -4 if the item is not found and should be placed here
list[4] =>returns -5 if the item is not found and should be placed here

The results would return -5 to 4...
What am I missing here?
 
Punit Singh
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
After list[4] =>returns -6 if the item is not found in list and should be placed at the last here
 
Christophe Verré
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are forgetting the case where you are looking for an element which is above the last one. For example, when you look for 6 in an array containing five elements (1,2,3,4,5), the index where 6 should be inserted is 5 : -5 - 1 = -6.

 
Duran Harris
Ranch Hand
Posts: 608
Eclipse IDE Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was thinking more along the lines of this:

Then should return -1.
Because "Ant" would precede any of the items in the list according to Sring's natural order and therefore be appropriate at index[0]...inverted and decremented:
Can't invert 0 but decrementing results in the index of [-1].
Likewise, should return [-3] to fit in between Dog and Mouse.

I don't think I understand this method
 
Punit Singh
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Try this, and tell me why were you wrong?
 
Duran Harris
Ranch Hand
Posts: 608
Eclipse IDE Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well I needed to import java.util.*; .
So then why is it that a collection of five elements :



inverted and decremented:


This would have a range of: -5 to 4.
Oh...I just noticed Christophe's post...Hehe...so this can actually return -6 to 4.What about the case where the item fits in at the beginning of the list??
 
Christophe Verré
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So then why is it that a collection of five elements :

Did you read my post ? You are thinking of putting values into an existing index instead of thinking of inserting values into a list. It should look more like this :

 
Punit Singh
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For beginning of list



this will work, and all elements will be shifted up by one.
 
Duran Harris
Ranch Hand
Posts: 608
Eclipse IDE Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Aha..now its clear..Thanks everyone
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic