Win a copy of The Little Book of Impediments (e-book only) this week in the Agile and Other Processes forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

BinarySearch Doubt

 
Hasnain Khan
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello All,
I am confused with the following code. Its taken from JQ+ and had a mistake but the following code is now fixed.

class MyStringComparator implements Comparator {
public int compare(Object o1, Object o2) {
System.out.println("o1 > " + o1);
System.out.println("");
System.out.println("o2 > " + o2);
System.out.println("");

int s1 = ((String) o1).length();
System.out.println("o1 length > " + s1);
System.out.println("");
int s2 = ((String) o2).length(); // it was o1 in JQ+
System.out.println("o2 length > " + s2);
System.out.println("");
int result = s1 - s2;
System.out.println("result > " + result);
System.out.println("");
return result;
}

public static void main(String args[]) {
String[] sa = { "d", "bbb", "aaaa" };
System.out.println("insertion point "
+ Arrays.binarySearch(sa, "cc", new MyStringComparator()) + "\n");
System.out.println("insertion point "
+ Arrays.binarySearch(sa, "c", new MyStringComparator())+ "\n");

}
}

The answer is -2 and 0 . Could some one kindly explain how is it -2 and 0. Since the array is not sorted, the results will be unpredictable -(insertion point) - 1 will be used.The comparator implementation is confusing me. The print statements show the arguments passed and notice that "aaaa" is not passed at all. Waiting for a favorable reply.
Kind Regards.
Hasnain Javed Khan.
 
Henry Wong
author
Marshal
Pie
Posts: 22113
88
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The answer is -2 and 0 . Could some one kindly explain how is it -2 and 0. Since the array is not sorted, the results will be unpredictable -(insertion point) - 1 will be used.



Read the JavaDocs again -- "-(insertion point) - 1" will be used only if the item is not found in the array. It still requires that the array is sorted. If the array is not sorted, then the results will be unpredictable, meaning what is returned is not defined.

Henry
 
pradeep singh
Ranch Hand
Posts: 339
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi
The overall meaning of your suggestion is that the output of above problem is unpredictable .AM I RIGHT?

It means when i run this above program on current version its output is different from when i run the same program on other version of jdk.AM I TRUE?


Please anybody help me in regarding this problem.
[ January 07, 2008: Message edited by: pradeep singh ]
 
Satya Maheshwari
Ranch Hand
Posts: 368
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Hasnain

In your question, you had mentioned:

Since the array is not sorted,


But per my understanding, the array is indeed sorted. I say this because the compare method in "MyStringComparator" just compares the string length to do the comparison. Hence "d", "bbb", "aaaa" is a sorted array.

The answer is -2 and 0 . Could some one kindly explain how is it -2 and 0.

For "cc", the string is not found in the array, but if would have been inserted at index 1(after d) to maintain the sorted order, hence the binary search returns (-1)-1=-2.

For "c", its equivalent to "d" as per your compare method, hence its found at index 0.

Please correct me if I missed something here.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic