• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • Devaka Cooray
Saloon Keepers:
  • Ganesh Patekar
  • Tim Moores
  • Carey Brown
  • Stephan van Hulst
  • salvin francis
Bartenders:
  • Ron McLeod
  • Frits Walraven
  • Pete Letkeman

BinarySearch Doubt  RSS feed

 
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.
 
author
Sheriff
Posts: 23603
138
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
 
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 ]
 
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.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!