aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Binary Search Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Binary Search" Watch "Binary Search" New topic
Author

Binary Search

Duran Harris
Ranch Hand

Joined: Nov 09, 2008
Posts: 598

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?

===>SCJP 1.5(72%)<===
==>SCWCD1.5(76%)<===
Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952
After list[4] =>returns -6 if the item is not found in list and should be placed at the last here


SCJP 6
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14688
    
  16

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.


[My Blog]
All roads lead to JavaRanch
Duran Harris
Ranch Hand

Joined: Nov 09, 2008
Posts: 598

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

Joined: Oct 16, 2008
Posts: 952


Try this, and tell me why were you wrong?
Duran Harris
Ranch Hand

Joined: Nov 09, 2008
Posts: 598

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

Joined: Nov 24, 2005
Posts: 14688
    
  16

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

Joined: Oct 16, 2008
Posts: 952
For beginning of list



this will work, and all elements will be shifted up by one.
Duran Harris
Ranch Hand

Joined: Nov 09, 2008
Posts: 598

Aha..now its clear..Thanks everyone
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary Search