• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Searching Arrays (K&B p. 577)

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I wanted to clarify that why is search result with and without comparator same, when the array searched is :

String [] sa = {"one", "two", "three", "four", "1", "2"}; //2 as compared to

String [] sa = {"one", "two", "three", "four"}; //1

In first case it doesn't matter whether comparator is passed in binary search. I wanted to clarify why is it happening that way?

class SearchObjArray {
public static void main(String args[]) {
//String [] sa = {"one", "two", "three", "four"}; // 1
String [] sa = {"one", "two", "three", "four", "1", "2"}; // 2

Arrays.sort(sa);
for (String s : sa)
System.out.print(s + " ");
System.out.println("\none = " + Arrays.binarySearch(sa, "one"));
System.out.println("now reverse sort");
ReSortComparator rs = new ReSortComparator();
Arrays.sort(sa, rs);
for (String s : sa)
System.out.print(s + " ");
System.out.println("\none = " + Arrays.binarySearch(sa, "one"));
System.out.println("one = " + Arrays.binarySearch(sa, "one", rs));
}

static class ReSortComparator implements Comparator<String> {
public int compare(String a, String b) {
return b.compareTo(a);
}
}
}

if case //1 is run the results are as mentioned in the book but when case //2 is run I get following results:

1 2 four one three two
one = 3
now reverse sort
two three one four 2 1
one = 2
one = 2

Thanks
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sajesh Adulkar wrote:
In first case it doesn't matter whether comparator is passed in binary search. I wanted to clarify why is it happening that way?




From the JavaDoc for Arrays binary search method....

Searches the specified array of bytes for the specified value using the binary search algorithm. The array must be sorted (as by the sort(byte[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.



In the case, where the comparator matches the way it is sorted, it works as advertised.

In the case, where the comparator does not match the way it is sorted, it is working by dumb luck. Try searching for a different element.

Henry
 
Sajesh Adulkar
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I checked and for all other entries except "one" it behaves as mentioned in the book - so why is it behaving in such a strange way for "one"? what to do if such a thing comes up in exam??
 
reply
    Bookmark Topic Watch Topic
  • New Topic