/*
 * Copyright (c) 2001 Matthew Feldt. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided the copyright notice above is
 * retained.
 *
 * THIS SOFTWARE IS PROVIDED ''AS IS'' AND WITHOUT ANY EXPRESSED OR
 * IMPLIED WARRANTIES.
 */

/**
 * Search.java
 *
 * Java Examples In A Nutshell Copyright (c) 2000 David Flanagan
 * Exercise 2-3:
 * Using the Sort.Comparer and/or Sort.Comparable interfaces, write a static
 * search() method for a class named Search that performs an efficient binary
 * search for a specified object within a sorted array of objects. If the object
 * is found in the array, search() should return the array index at which it is
 * located. Otherwise, it should return -1.
 *
 * @author Matthew Feldt <developer@feldt.com>
 * @version 1.0, 01/29/2001 13:59
 */

package com.feldt.examples.classes;
import com.davidflanagan.examples.classes.Sorter;

class Search {
	/**
	 * Binary search for an object (needle) in a sorted object array (haystack).
	 * Objects are comparer by implementing interface Sorter.Comparer (c).
	 */
	public static int search(Object[] haystack, Object needle, Sorter.Comparer c) {
		int middle = 0, low = 0, high = haystack.length-1;

		// binary search...
		while (low <= high) {
			middle = (high+low)/2;
			if (c.compare(needle, haystack[middle]) > 0) {
				high = middle-1;
			}
			else if (c.compare(needle, haystack[middle]) < 0) {
				low = middle+1;
			}
			else { low = middle; break; }
		}

		if (c.compare(haystack[middle], needle) == 0) return middle;
		else return -1;
	}

	/** test class */
	static class Test {
		public static void main (String args[]) {
			final int SIZE = 10;
			Double[] doubleArray = new Double[SIZE];
			int searchIndex;

			// create an array of randle Doubles
			for (int i = 0; i < doubleArray.length; i++) {
				doubleArray[i] = new Double(Math.random() * 100);
			}

			// implement interface Sorter.Comparer() and sort the array
			// using David Flanagan's Sorter class
			Sorter.Comparer doubleComparer = new Sorter.Comparer() {
				public int compare(Object a, Object b) {
					return ((Double)a).compareTo((Double)b);
				}
			};
			Sorter.sort(doubleArray, 0, doubleArray.length-1, false, doubleComparer);

			// print the array
			for (int i = 0; i < doubleArray.length; i++) {
				System.out.println(doubleArray[i]);
			}

			// search for each value in the array
			for (int i = 0; i < doubleArray.length; i++) {
				searchIndex = Search.search(doubleArray, doubleArray[i], doubleComparer);
				System.out.println("Searching for " + doubleArray[i] +
					", Search.search() = " + searchIndex);
			}

			// guessing pi didn't occur randomly in the array...
			searchIndex = Search.search(doubleArray, new Double(Math.PI), doubleComparer);
			System.out.println("Searching for " + Math.PI +
				", Search.search() = " + searchIndex);
		}
	}
}