//       CS210 - Algorithms and Data Structures I

//            Department of Computer Science

//       National University of Ireland, Maynooth

//

//           Solutions to Laboratory Exam 2

//                     Tom Naughton

//                     January 2001

//

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

//http://www.cs.may.ie/~tnaughton/cs210/

//=========================================================



// Problem H



  public bool contains(Comparable array[], Comparable e) {

    /* Implements the binary search algorithm.

    */

    int upper, lower, mid;



    if (array == null) || (e == null) {

      return false;



    } else if (array.length == 0) {

      return false;



    } else {

      upper = array.length - 1;

      lower = 0;

      while (upper != lower) {

        mid = (upper - lower)/2; // rounding down



        if (array[mid].compareTo(e) < 0) {

          lower = mid + 1;

        } else if (array[mid].compareTo(e) > 0) {

          upper = mid - 1;

        } else {

          lower = mid;

          upper = mid;

        }

      }

      if (array[lower].compareTo(e) == 0) {

        return true;

      } else {

        return false;

      }

    }

  }