//---------------------------------------------------------
// linearSearch
//
// Returns: The index of the record corresponding to stuID
//    if such a record exists. Otherwise, this function
//    returns a value of -1.
//
// In Parameters: stuID, idArr, n
//---------------------------------------------------------
int linearSearch(string stuID, const string idArr[], int n)
{
    int pos;      // Position of desired record
    bool found;   // True when stuID is found
    
    pos = n - 1;  // Start looking at the end
    found = false;
    
    while(!found && pos >= 0)
    {
        found = (idArr[pos] == stuID);
        if (!found)
        {
            pos--;
        }
    }
    return pos;
}

//---------------------------------------------------------
// binarySearch
//
// Returns: The index of the record corresponding to stuID
//    if such a record exists. Otherwise, this function
//    returns a value of -1.
//
// Precondition: the list of student ids has been has been
//   sorted in ascending order.
//
// In Parameters: stuID, idArr, n
//---------------------------------------------------------
int binarySearch(string stuID, const string idArr[], int n)
{
    int pos;         // Position of desired record
    bool found;      // True when stuID is found
    int left;        // Left end of sublist
    int right;       // Right end of sublist
    int middle;      // Middle of sublist
    
    found = false;
    left = 0;
    right = n - 1;
    while(left <= right && !found)
    {
        middle = (left + right) / 2;
        if (stuID < idArr[middle])
        {
            right = middle - 1;
        }
        else if (stuID > idArr[middle])
        {
            left = middle + 1;
        }
        else
        {
            found = true;
        }
    }
    
    if (found)
    {
        pos = middle;  // Successful search
    }
    else
    {
        pos = -1;  // Unsuccessful search
    }
    
    return pos;
}