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
import chapter2.MyInput;

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);
  }
}