Searching a String Array, Code Incorrectly States String Value Is Found

I am trying to make a template for a binary search algorithm. The algorithm works perfectly when I am looking for a specific integer, or a string. I get back the index key when when I search for a specific value for both a string and an integer array.

If I search for an integer that isn't in the array, a "not found" populates correctly.

However, when I search for a string that isn't in the string array, the console tells me, "value is in the index location -858993560."

No matter what string value I try and search for, I always get that the value is in the index location above.

The string isn't in the index though. I have looked through the code, I looked for other answers but nothing is sticking out at me.

When I search for a value that I know isn't in the array, why does the console tell me it is in the array at this large negative index block?

Here is my code below.

#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

template<class T>
void search_array(const T a[], int first, int last, T& key, bool& found, int& location)
{
    int mid;
    if (first > last)
    {
        found = false;
    }
    else
    {
        mid = (first + last) / 2;
        if (key == a[mid])
        {
            found = true;
            location = mid;
        }
        else if (key < a[mid])
        {
            search_array(a, first, mid - 1, key, found, location);
        }
        else if (key > a[mid])
        {
            search_array(a, mid + 1, last, key, found, location);
        }
    }

}

int main()
{

    int a[] = { 0, 1, 1, 2, 3, 5, 6, 13, 21, 32, 55, };
    const int finalIndex = 10 - 1;
    int key, location;
    bool found;

    cout << "Integer Test array contains: \n";

    for (int i = 0; i < 10; i++){
        cout << a[i] << " " ;
    }
    cout << "\nEnter number to be located: ";
    cin >> key;
    search_array(a, 0, finalIndex, key, found, location);
    if (found)
        cout << key << " is in index location "
        << location << endl;
    else
        cout << key << " is not in the array." << endl;

    string b[] = { "head", "knees", "shoulders", "toes" };
    const int stringFinalIndex = 4 - 1;
    string key1;
    int location1;
    bool found1;

    cout << "String Array contains: \n";

    for (int i = 0; i < 4; i++){
        cout << b[i] << " ";
    }
    cout << "Enter string to be located: ";
    cin >> key1;
    search_array(b, 0, stringFinalIndex, key1, found1, location1);
    if (found)
        cout << key1 << " is in index location "
        << location1 << endl;
    else
        cout << key1 << " is not in the array." << endl;

system("PAUSE");
return 0;

}