2 replies to this topic

[johnsonk]

I was looking through some lectures in my university and found the following code a bit odd:

[SIZE=2][SIZE=2][FONT=Arial]// [SIZE=2][SIZE=2]assume [/SIZE][/SIZE][SIZE=2][SIZE=2]SomeType[/SIZE][/SIZE][/FONT][FONT=Arial][SIZE=2][SIZE=2]implements [/SIZE][/SIZE][SIZE=2][SIZE=2]Comparable[/SIZE][/SIZE][SIZE=2][SIZE=2]:[/SIZE][/SIZE][/FONT]
 [SIZE=2][SIZE=2][FONT=Arial]List<[/FONT][/SIZE][/SIZE][SIZE=2][SIZE=2][FONT=Arial]SomeType[/FONT][/SIZE][/SIZE][FONT=Arial][SIZE=2][SIZE=2]> seq = new ArrayList<[/SIZE][/SIZE][SIZE=2][SIZE=2]SomeType[/SIZE][/SIZE][/FONT][SIZE=2][SIZE=2][FONT=Arial]>();[/FONT][/SIZE][/SIZE]
 
[LEFT][SIZE=2][SIZE=2][FONT=Arial]boolean insert([/FONT][/SIZE][/SIZE][SIZE=2][SIZE=2][FONT=Arial]SomeType [/FONT][/SIZE][/SIZE][SIZE=2][SIZE=2][FONT=Arial]item) {[/FONT][/SIZE][/SIZE][/LEFT]
[SIZE=2][SIZE=2][FONT=Arial]int bsRes = Collections.binarySearch(seq,item);[/FONT][/SIZE]
 
 
[SIZE=2][FONT=Arial]if (bsRes >= 0) { // item [/FONT][/SIZE]
[LEFT][/SIZE][SIZE=2][FONT=Arial][SIZE=2]found in [/SIZE][/FONT][/SIZE][SIZE=2][SIZE=2][FONT=Arial]seq[/FONT][/SIZE][/SIZE][/LEFT]
 
 
[LEFT][SIZE=2][SIZE=2][FONT=Arial]return false; // [/FONT][/SIZE][/SIZE][SIZE=2][SIZE=2][FONT=Arial]ie, list does not get updated[/FONT][/SIZE][/SIZE]

[SIZE=2][SIZE=2][FONT=Arial]}[/FONT][/SIZE][/SIZE]
[LEFT][SIZE=2][SIZE=2][FONT=Arial]else { // item [/FONT][/SIZE][/SIZE][SIZE=2][FONT=Arial][SIZE=2]not found in [/SIZE][/FONT][/SIZE][SIZE=2][SIZE=2][FONT=Arial]seq[/FONT][/SIZE][/SIZE]
[SIZE=2][SIZE=2][FONT=Arial]seq.add([COLOR=red]item, [/COLOR][/FONT][/SIZE][/SIZE][SIZE=2][SIZE=2][FONT=Arial][COLOR=red]-(bsRes + 1)[/COLOR][/FONT][/SIZE][/SIZE][FONT=Arial][SIZE=2][SIZE=2][COLOR=black]);[/COLOR]// [/SIZE][/SIZE][SIZE=2][SIZE=2]add element at correct insertion position![/SIZE][/SIZE][/FONT][/LEFT]
[/LEFT]

 
 
 
 
 
[LEFT][SIZE=2][SIZE=2][FONT=Arial]return true; // [/FONT][/SIZE][/SIZE][SIZE=2][SIZE=2][FONT=Arial]ie, list has been updated by inserting element[/FONT][/SIZE][/SIZE]

[SIZE=2][FONT=Arial][SIZE=2]}[/SIZE][/FONT][/SIZE][/LEFT]

 
 
 
[/SIZE][/SIZE]

I may be wrong but there are two things I find two things odd about this code. Adding objects to a List require the index as the first parameter:

add(int index, Object element)

Not only this but I don't see why you would ise "bsRes +1" as the index, this would surely cause an out of bounds exception.

The way I would have done it is:

[FONT=Arial]seq.add([/FONT][SIZE=2][SIZE=2][FONT=Arial]-(bsRes - 1), item[/FONT][/SIZE][/SIZE][FONT=Arial][SIZE=2][SIZE=2]); // [/SIZE][/SIZE][SIZE=2][SIZE=2]add element at correct insertion position![/SIZE][/SIZE][/FONT]

Please let me know if I am mistaken.

[johnsonk]

Anyone?

[ThemePark]

This is taken from the Java Doc for the binarySearch method:

Quote

the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

So that ensures that the number returned will always be negative, if the element doesn't exist in the List. So in order to get the insertion point, it's necessary to reverse the calculations made by the binarySearch methods, which is done in the example you posted. If you removed the brackets, your own example would work just as well.

As far as List.add, there's also an add method where you just specify the element to add, and it's then added to the end of the list.