package psJava;

public class IntArray {

  /* postcondition: Returns the subscript of the first element
   *   of its array argument that stores the target value.
   *   Returns -1 if target is not found.
   */ 
  public static int search(int[] x, int target) {
     for (int i = 0; i < x.length; i++) {
        if (x[i] == target)
           return i;        //index of target
     }

     // All elements tested without success.
     return -1;
  }

  // postcondition: the values in its array argument are
  //   in increasing order.
  public static void selectionSort(int[] x) {

     int posMin;       //index of next smallest element
     int temp;         //temporary value for exchange

     for (int fill = 0; fill < x.length-1; fill++) {
        /* invariant:
         *   The elements in x[0] through x[fill-1] are in
         *   their proper place and fill < x.length is true.
         */
        // Find position of smallest element in the subarray
        //   starting at element x[fill].
        posMin = findPosMin(x, fill);

        //Exchange elements with subscripts fill and posMin.
        temp = x[fill];
        x[fill] = x[posMin];
        x[posMin] = temp;
     }
  }


  // postcondition: returns the position of the smallest
  //   element in array x from x[fill] to the end
  private static int findPosMin(int[] x, int fill) {
     // Assume smallest value is at position fill
     int posMinSoFar = fill;

     // Remember any smaller value found in the array.
     for (int i = fill + 1; i < x.length; i++) {
        if (x[i] < x[posMinSoFar])
          posMinSoFar = i;
     }

     // posMinSoFar is subscript of smallest element
     return posMinSoFar;
  }

  // postcondition: Returns the median value stored
  //   in its array argument.
  public static int findMedian(int[] x) {
    // Create a copy of array x.
    int[] copyX = new int[x.length];
    System.arraycopy(x, 0, copyX, 0, x.length);

    // Sort array copyX.
    selectionSort(copyX);

    // Return middle value or average of two "middle" values.
    if (x.length % 2 == 1)
       return copyX[x.length/2];   // odd size array
    else
       return (copyX[x.length/2 - 1] +
               copyX[x.length/2]) / 2;  // even size
  }

}