wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes BinarySearch Doubt 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 "BinarySearch Doubt" Watch "BinarySearch Doubt" New topic
Author

BinarySearch Doubt

Hasnain Khan
Ranch Hand

Joined: Dec 15, 2007
Posts: 44
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
Sheriff

Joined: Sep 28, 2004
Posts: 18760
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
pradeep singh
Ranch Hand

Joined: Oct 23, 2007
Posts: 339
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 ]

SCJP 5.0(75%), SCWCD 5.0(88%)
Satya Maheshwari
Ranch Hand

Joined: Jan 01, 2007
Posts: 368
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.


Thanks and Regards
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: BinarySearch Doubt