Comparer interfaces and efficient binary search?

[DJP]

For my grade 12 programming class, we are learning how to use objects, classes, and interfaces, and I have this assignment that I don't understand:

Quote:

Using the Sort.Comparer and/or the Sort.Comparable interfaces, write a static search () method for a class named Search that performs an efficient binary search for a specific object within a sorted array of object. If the object is found in the array, search() should reutrn the array index at which it is located. Otherwise, it should return -1.

Although I understand what I'm expected to ouput, I don't understand how to implement the Sort.Comparer and/or Sort.Comparable interfaces and I have no idea what an efficient binary search is. This assignment was photocopied out of a book by David Flannagan if that helps.

Any help would be appreciated.

Also, is there a way to draw graphics (rectangle, circle etc) in the standard input/output console (we use Ready to Program Java, but this isn't the HSA console). We were assigned a circle program which nobody understood, and then the teacher couldn't explain why the example program (a rectangle) which was taken right from this book wouldn't display a rectangle on the screen. Needless to say we didn't end up having to do the circle.

[wtd]

Could you please post the Sort.Comparer/Comparable interface(s), as I'm not sure if this is the same Comparable interface that's in the standard Java librariers, or something custom.

[DJP]

I think this is it. The teacher mentioned something about it being on our school's handout drive, and this was the only file that looked like it was it. If this isn't it then the question probably refers to the standard java library. It was in a fle called Sorter.java

code:

Never mind this

[wtd]

Ok. The question I should ask is: do you understand how to do a binary search?

[DJP]

Not really no.

[McKenzie]

Hmm,
It seems to me the bulk of the problem has to do with your teacher. It seems that he is using a book that he doesn't fully understand to get you to make code that you have no clue about. I could show you binary search from scratch (and will if you ask), but the way it is actually done looks something like:

code:

import java.util.*; class Search {     public static void main(String args[]) {         int []junk= {4,34,2,423,4,234,34,23,4,2,2,67,7,68,56,56,435,34,54};         List jnk = new ArrayList();         for(int i =0;i<junk.length;i++)             jnk.add(new Integer(junk[i]));         Collections.sort(jnk);         System.out.println(Collections.binarySearch(jnk,new Integer(67)));     } }

You'll note that no matter what you are using for the Binary Search it MUST be sorted first. Above are some simple collections in Java.

[wtd]

Ok... ever played a game where someone asks you to guess a number they're thinking of, and tells you if you're high or low? That's basically a binary search.

Let's say I'm looking for the number 7 in a list of numbers:

1, 3, 4, 5, 6, 7, 11, 12, 15, 21, 22, 23, 26, 33, 34, 39, 41, 42, 98, 101

That's 20 numbers. They're already sorted.

So, for my first "guess" I look at the entire list from index 0 to index 19. I pick the middle index (9) and look at that number. The number 21 is at index 9. So, my first guess is too high. Now I look at just that half of the list, from index 0 to index 8.

The midpoint of that is index 4. The number 6 is at index 4. 6 is smaller than 7, so the number we're looking for has to be between index 5 and 8.

The midpoint of that is index 6. The number at index 6 is 11. That's too big, so we know it has to be index 5. Indeed, if we look at index 5, we find the value 7.

[DJP]

Alright, the binary search now makes sense to me. My class has never been taught this before.

So now that I got the binary search, can I finish this assignment, or is there something else I need to know with the Sort.Comparer/Comparable interfaces?

[wtd]

Basically all the Comparable interface (which is a copy of the standard Comparable interface, whereas the "Comparer" interface is not standard) does is provide a compareTo method.

The compareTo method takes two objects/values and compares them to see if they're equal or if one is greater than or less than the other. If they're equal it returns zero. If less than, a negative number is returned. If greater than, a positive number is returned.

[McKenzie]

The place to go for a proper understanding is SUN
http://java.sun.com/docs/books/tutorial/collections/interfaces/order.html
I know at first it's daunting but once you understand collections comparators and binary Searching using them are a piece of cake.

[wtd]

And the basic concept of the comparator is used in every language I've yet encountered.