aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes arrays binarysearch - undefined thingy K&B p558 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 "arrays binarysearch - undefined thingy K&B p558" Watch "arrays binarysearch - undefined thingy K&B p558" New topic
Author

arrays binarysearch - undefined thingy K&B p558

Robert Elbourn
Ranch Hand

Joined: Oct 15, 2007
Posts: 69
Line 4 (section) states that if you dont pass a comparator used to sort an array you get an incorrect (undefined) answer.....

whats the whole undefined thing?

If I binary search an unsorted array I still get an answer (positive integer) if I search a sortedwithacomparator but dont pass the comparator to binary search then I get a negative number (as you might expect) being an insertion point.

So my question is: does undefined mean "you could get any value back"?

thanks in advance

code below:

package revision;

import java.util.Arrays;
import java.util.Comparator;

public class BinarySearchTester {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

String [] array = {"one","two","three","four","five","six","zed"};

for (String s : array) {
System.out.println("UnSorted:"+s);
}
ReSortComparator reSort = new ReSortComparator();

//Arrays.sort(array);
Arrays.sort(array,reSort);

for (String s : array) {
System.out.println("IsSorted:"+ s);
}

System.out.println(Arrays.binarySearch(array,"three"));
//System.out.println(Arrays.binarySearch(array,"three",reSort));
}

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

}





I did get an answer









HP-BBQ, Ketchup
Pranav Bhatt
Ranch Hand

Joined: Mar 20, 2006
Posts: 284
Robert,


whats the whole undefined thing?

If I binary search an unsorted array I still get an answer (positive integer) if I search a sortedwithacomparator but dont pass the comparator to binary search then I get a negative number (as you might expect) being an insertion point.

So my question is: does undefined mean "you could get any value back"?


The Undefined here inmplies that if you dont sort the array with comparator or the array is an unsorted one you would get an unexpected result. As i ran your code and was getting -7 and -8 with unsorted and no comparator respectively as the insertion points, which you can judge are wrong places. Positive integer gives you the position of searched starting with 0 and negative gives you the insertion point(eg. if you get -8 then insertion point is (-(-8)-1) =7th place, again starting with 0)
I hope the below changes will make things clear-:

package mocks;

import java.util.Arrays;
import java.util.Comparator;

public class BinarySearchTester {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

String [] array = {"one","two","three","four","five","six","zed"};

for (String s : array) {
System.out.println("UnSorted:"+s);
}
System.out.println("Without sorting "+Arrays.binarySearch(array,"three"));
ReSortComparator reSort = new ReSortComparator();

Arrays.sort(array);
for (String s : array) {
System.out.println("Sorted:"+s);
}
System.out.println("After sorting "+Arrays.binarySearch(array,"three"));


Arrays.sort(array,reSort);

for (String s : array) {
System.out.println("IsSorted:"+ s);
}

System.out.println("Without comparator "+Arrays.binarySearch(array,"three"));
System.out.println("With comparator "+Arrays.binarySearch(array,"three",reSort));
}


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

}

The output is as follows-:

UnSorted: one
UnSorted:two
UnSorted:three
UnSorted:four
UnSorted:five
UnSorted:six
UnSorted:zed
Without sorting -7
Sorted:five
Sorted:four
Sorted: one
Sorted:six
Sorted:three
Sorted:two
Sorted:zed
After sorting 4
IsSorted:zed
IsSorted:two
IsSorted:three
IsSorted:six
IsSorted: one
IsSorted:four
IsSorted:five
Without comparator -8
With comparator 2



Thanks

[ January 09, 2008: Message edited by: pranav bhatt ]
[ January 09, 2008: Message edited by: pranav bhatt ]
Robert Elbourn
Ranch Hand

Joined: Oct 15, 2007
Posts: 69
I see thanks! Its just the "undefined" wording they use in the books and on one of the exam questions (in whizzlabs I think) ... I'll take a look at rerunning the code when I get home it seems unusual that its -7 for one then -8 for another, it seems they are both insertion points, but also both incorrect!
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8813
    
    5
The API often uses the word "undefined". I think in this case you might want to insert the word "unpredictable". Presumably, other than when you call Math.random, you want your programs to behave predictably.


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: arrays binarysearch - undefined thingy K&B p558