//**************************************************************
//
//  CS 240B   Winter Quarter 2003 Ohio University Travis Dillon
//  Proj2   : Array Workshop
//  file    : search_sort.cc  
//  started : 01-16-03
//
//**************************************************************

#include "search_sort.h"
#include "prog2.h"
#include "menu_print.h"
#include "fill.h"

int find_max(int x[], int array_sz)
{
   int location(0);
   int value(x[location]);
   
   for(int i(1); i < array_sz; ++i)
   {  //increment through array till biggest element is found
      if(x[i] > value)
      {
         location = i;
         value = x[i];
      }
   }
   return location;
}

void swap(int x[], int end, int max)
{  //used to swap values for sorting
   int temp(x[end]);
   x[end] = x[max];
   x[max] = temp;
}

void sort(int x[], int array_sz)
{
   int end(array_sz - 1);
   int max;
   
   while(end > 0)
   {  //selection sort
      max = find_max(x, end + 1);
      swap(x, end, max);
      --end;
   }
}

int lin_search(int x[], int array_sz, int target)
{
   int i;
   for(i=0 ; i < array_sz; ++i)
   {  //search though array from beginning to end for target
      if(x[i] == target)
      {
         return i;
      }
   }
   return i;
}

int bin_search(int x[], int array_sz, int target)
{
   int l(0);
   int r(array_sz - 1);
   int m;
   
   while(l <= r)
   {  //binary search locates target in O(log n)
      m = (l + r)/2;
      
      if(x[m] == target)
      {
         return m;
      }
      else if(x[m] > target)
      {
         r = m-1;
      }
      else if(x[m] < target)
      {
         l = m+1;
      }
   }
   return array_sz;
}