Binary Search

[Duran Harris]

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]

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

[Christophe Verré]

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.

List<String> l = new ArrayList<String>();
l.add("1");
l.add("2");
l.add("3");
l.add("4");
l.add("5");
System.out.println(Collections.binarySearch(l, "6"));

[Duran Harris]

I was thinking more along the lines of this:

import static java.util.Collections.*;

List<String> list= new ArrayList<String>();
list.add("Dog");
list.add("Cat";);
list.add("Mouse");
sort(list) //Don't think I need a comparator(String has natural order)

Then

binarySearch(list,"ant")

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,

binarySearch(list,"elephant")

should return [-3] to fit in between Dog and Mouse.

I don't think I understand this method

[Punit Singh]

  List<String> list= new ArrayList<String>(); 
	list.add("Dog"); 
	list.add("Cat"); 
	list.add("Mouse"); 
	Collections.sort(list); //Don't think I need a comparator(String has natural order) 

	System.out.println(Collections.binarySearch(list,"Ant"));
	System.out.println(Collections.binarySearch(list,"Elephant"));
	System.out.println(Collections.binarySearch(list,"None"));  

Try this, and tell me why were you wrong?

[Duran Harris]

Well I needed to import java.util.*; .
So then why is it that a collection of five elements :

[0][1][2][3][4]

inverted and decremented:

[0] becomes [-1]
[1] becomes [-2] 
[2] becomes [-3]
[3] becomes [-4]
[4] becomes [-5]

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é]

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 :

    <-- insert here (at 0, so -1)
[0] aaa
    <-- insert here (at 1, so -2)
[1] bbb
    <-- insert here (at 2, so -3)
[2] ccc
    <-- insert here (at 3, so -4)
[3] ddd
    <-- insert here (at 4, so -5)
[4] eee
    <-- insert here (at 5, so -6)

[Punit Singh]

For beginning of list

[0] becomes [-1] 

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

[Duran Harris]

Aha..now its clear..Thanks everyone