Win a copy of Design for the Mind this week in the Design forum!

# Binary Search

Duran Harris
Ranch Hand
Posts: 608
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?'

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
After list[4] =>returns -6 if the item is not found in list and should be placed at the last here

Sheriff
Posts: 14691
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.

Duran Harris
Ranch Hand
Posts: 608
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

Try this, and tell me why were you wrong?

Duran Harris
Ranch Hand
Posts: 608
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??

Sheriff
Posts: 14691
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
Posts: 952
For beginning of list

this will work, and all elements will be shifted up by one.

Duran Harris
Ranch Hand
Posts: 608
Aha..now its clear..Thanks everyone