binarysearch.java

此源码为机械工业出版社出版的《Java语言程序设计》第三版所配套的书中所有源代码。

// 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 up = list.length - 1;
    return binarySearch(key, list, low, up);
  }

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

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

    return -1;
  }
}