• 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
  • Ron McLeod
  • Paul Clapham
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Rob Spoor
  • Bear Bibeault
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Piet Souris
Bartenders:
  • Frits Walraven
  • Himai Minh

arrays binarysearch - undefined thingy K&B p558

 
Ranch Hand
Posts: 69
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 284
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 69
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
author
Posts: 9025
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic