// This program demonstrates the searchList function, which
// performs a linear search on an integer array.
#include <iostream>
using namespace std;

// Function prototype
int searchList(int [], int, int);


int main()
{
   int n;
   int rnum;
   cout << "Linear Search  Algorithm \nHow big an array would you like? ";
   cin >> n;
    cout << "What number would you like to search for in this array [ between 0 - "<< n << "]? ";
   cin >> rnum;
   int values[n];
   for(int i = 0; i < n; i++)
   	   values[i] = rand()%(n+1);

   // Search the array for rnum.
   int results = searchList(values, n, rnum);
   
   // If searchList returned -1, then number was not found.
   if (results == -1)
      cout << "Sorry, there were no instances of "<< rnum << " found in the array\n";
   else
   {
      // Otherwise results were found
      cout << "The number " << rnum << " was located at index ";
      cout << (results + 1) << endl;
   }
   system("pause");
}

//*****************************************************************
// The searchList function performs a linear search on an         *
// integer array. The array list, which has a maximum of numElems *
// elements, is searched for the number stored in value. If the   *
// number is found, its array subscript is returned. Otherwise,   *
// -1 is returned indicating the value was not in the array.      *
//*****************************************************************

int searchList(int list[], int numElems, int value)
{
   int index = 0;       // Used as a subscript to search array
   int position = -1;   // To record position of search value
   bool found = false;  // Flag to indicate if the value was found

   while (index < numElems && !found)
   {
      if (list[index] == value)  // If the value is found
      {
         found = true;           // Set the flag
         position = index;       // Record the value's subscript
      }
      index++;                   // Go to the next element
   }
   return position;              // Return the position, or -1
}