//********************************************************************
//  Searches.java       Author: Lewis/Loftus/Cocking
//
//  Demonstrates the linear and binary search algorithms.
//********************************************************************

public class Searches
{
   //-----------------------------------------------------------------
   //  Searches the array of integers for the specified element using
   //  a linear search. The index where the element was found is
   //  returned, or -1 if the element is not found.
   //-----------------------------------------------------------------
   public static int linearSearch (int[] numbers, int key)
   {
      for (int index = 0; index < numbers.length; index++)
         if (key == numbers[index])
            return index;
      return -1;
   }

   //-----------------------------------------------------------------
   //  Searches the array of integers for the specified element using
   //  a binary search. The index where the element was found is
   //  returned, or -1 if the element is not found.
   //  NOTE: The array must be sorted!
   //-----------------------------------------------------------------
   public static int binarySearch (int[] numbers, int key)
   {
      int low = 0, high = numbers.length-1, middle = (low + high) / 2;

      while (numbers[middle] != key && low <= high)
      {
         if (key < numbers[middle])
            high = middle - 1;
         else
            low = middle + 1;
         middle = (low + high) / 2;
      }

      if (numbers[middle] == key)
         return middle;
      else
         return -1;
   }
}

Classwork: Work on this two assignments

1. Given the following list of numbers, how many elements of the list would be examined by the linear search algorithm to determine if each of the indicated target elements are on the list? Trace the steps on paper.

15   21   4   17   8   27   1   22   43   57  25   7   53   12   16

a. 17
b. 15
c. 16
d. 45

1. Describe the general concept of a binary search. Tell the story and be creative.

2. Given the following list of numbers, how many elements of the list would be examined by the binary search algorithm to determine if each of the indicated target elements are on the list? Trace the steps on paper and hand it in.

1   4   7   8   12   15   16   17   21   22   25   27   43   53   57

a. 17
b. 15
c. 57
d. 45

Assignments:
Self-Review 6.9 and 6.10
MC 6.5
T/F 6.7