arrays binarysearch - undefined thingy K&B p558

[Robert Elbourn]

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]

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]

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]

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.