import java.awt.*;
import java.awt.event.*;
import java.util.Random;

class BinarySearchAlgorithm
{
	public static int search(int[] array, int target)
	/////////////////////////////////////////////////////////////////////
	// Preconditions: 
	//		array is sorted from smallest to largest. It
	//		may contain multiple entries with the same value.
	//
	// Postconditions:
	//		The array is unmodified.
	//
	// Return value:
	//		The index in the array where the target is
	//		found. If the target is at more than one index an
	//		arbitrary index where the target is found is returned.
	//		If the target is not in the array the return value is -1.
	/////////////////////////////////////////////////////////////////////
	{
		// INSERT CODE HERE
		return -1;
	}
}


public class SearchDemo extends Panel implements ActionListener
{
	private int[] numbers;
	private Toolkit toolKit = Toolkit.getDefaultToolkit();
	private List listOfNumbers = new List();
	private TextField target = new TextField(7);
	private Button load = new Button("Reload");
	private Button find = new Button("Search");
		
	public SearchDemo(int size)
	{
		numbers = new int[size];
		loadData(numbers);
		
		setLayout(new GridLayout(1,2));
		add(listOfNumbers);
		Panel p = new Panel();
		p.add(new Label("Target:"));
		p.add(target);
		p.add(load);
		p.add(find);
		add(p);
		
		load.addActionListener(this);
		find.addActionListener(this);
	}
	
	
	public void actionPerformed(ActionEvent e)
	{
		if (e.getSource() == load)
			loadData(numbers);
			
		else if (e.getSource() == find) {
			int n = Integer.parseInt(target.getText());
			int index = BinarySearchAlgorithm.search(numbers, n);
			if (index == -1) {
				listOfNumbers.select(numbers.length); // "Not Found"
				listOfNumbers.makeVisible(numbers.length);
			}
			else {
				listOfNumbers.select(index);
				listOfNumbers.makeVisible(index);
			}
		}
	}
	
	private int nextInt(int n, Random r)
	{
    	if (n<=0)
			throw new IllegalArgumentException("n must be positive");

     	if ((n & -n) == n)  // i.e., n is a power of 2
        	return (int)((n * (long)r.nextInt()) >> 31);

    	int bits, val;
    	do {
        	bits = r.nextInt();
        	val = bits % n;
    	} while(bits - val + (n-1) < 0);
    	return val;
	}
 

	private void loadData(int[] nums)
	{
		Random r = new Random();
		nums[0] = nextInt(10, r); // random number between 0 and 9 inclusive
		
		listOfNumbers.removeAll();
		listOfNumbers.add("" + nums[0]);
		
		for (int i = 1; i < nums.length; i++) {
			nums[i] = nums[i-1] + nextInt(3, r);
			listOfNumbers.add("" + nums[i]);
		}
		
		listOfNumbers.add("Not Found");
	}
	
	public static void main(String args[])
	{
		Frame f = new Frame();
		f.add(new SearchDemo(500));
		f.resize(200, 400);
		f.addWindowListener(new WindowCloser());
		f.show();
	}
}

class WindowCloser extends WindowAdapter
{
	public void windowClosing(WindowEvent e)
	{
		System.exit(0);
	}
}