// package chapter5;

/**
 * Title:        Chapter 5, "Arrays"
 * Description:  Examples for Chapter 2
 * Copyright:    Copyright (c) 2000
 * Company:      Armstrong Atlantic State University
 * @author Y. Daniel Liang
 * @version 1.0
 */

// BinarySearch.java: Search a key in a sorted list

public class BinarySearch
{
  /**Main method*/
  public static void main(String[] args)
  {
    int[] list = new int[10];

    // Create a sorted list and display it
    System.out.print("The list is  ");
    for (int i=0; i<list.length; i++)
    {
      list[i] = 2*i + 1;
      System.out.print(list[i] + "  ");
    }
    System.out.println();

    // Prompt the user to enter a key
    System.out.print("Enter a key  ");
    int key = MyInput.readInt();
    int index = binarySearch(key, list);
    if (index != -1)
      System.out.println("The key is found in index " + index);
    else
      System.out.println("The key is not found in the list");
  }

  /**Use binary search to find the key in the list*/
  public static int binarySearch(int key, int[] list)
  {
    int low = 0;
    int high = list.length - 1;
    return binarySearch(key, list, low, high);
  }

  /**Use binary search to find the key in the list between
     list[low] list[high]*/
  public static int binarySearch(int key, int[] list,
    int low, int high)
  {
    if (low > high)  // The list has been exhausted without a match
      return -1;

    int mid = (low + high)/2;
    if (key < list[mid])
      return binarySearch(key, list, low, mid-1);
    else if (key == list[mid])
      return mid;
    else
      return binarySearch(key, list, mid+1, high);
  }
}

//------------

// a class for reading various types from the keyboard (System.in) 
class MyInput
{
    public static String readString()
    {
        String string = "";
        java.io.BufferedReader bufferedReader = 
           new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
        try
        {
            string = bufferedReader.readLine();
        }
        catch (java.io.IOException ex)
        {
            throw new RuntimeException(ex);
        }
        return string;
    }

    public static int readInt()
    {
        return Integer.parseInt(readString());
    }

    public static double readDouble()
    {
        return Double.parseDouble(readString());
    }

    // test all the methods of this class
    public static void main(String[] args)
    {
        System.out.println("Testing 'readString()'");
        System.out.print("Input your string : ");
        System.out.println("Your string was '" + readString() + "'");
        System.out.println("\nTesting 'readInt()'");
        System.out.print("Input your int : ");
        System.out.println("Your int was '" + readInt() + "'");
        System.out.println("\nTesting 'readDouble()'");
        System.out.print("Input your double : ");
        System.out.println("Your double was '" + readDouble() + "'");
    }
}