O problema está nos trechos que você aloca uma nova `string` assim:

    new char[std::strlen(first_name)];

Deveria ser:

    new char[std::strlen(first_name) + 1];

Sem o `+ 1` você não está considerando o caractere nulo da string `\0`, que causa nenhum problema em seu programa até o destrutor de `patientType` ser chamado. E isso corre quando você adiciona novos pacientes e quando lista eles.

---

Outros detalhes:

1. Na função `patientType::get()` as variáveis `first_name` e `second_name` devem ser deletadas usando `delete []` (igual você fez no destrutor) e não apenas `delete`.<br>
2. Em `patientType::operator=(const patientType& patient)` você deve verificar e deletar os valores anteriores (ou limpar) das strings antes de alocar novas strings.
3. Quando você faz `return first.second_name() == second.second_name();` você está comparando ponteiros, para comparar o valor das strings use `strcmp()`.
4. E por último, quando você chama a função `binary_search(T* var, T term, unsigned size, BinaryCompare compare_operation)` você está copiando o objeto `T term`. Isso significa que toda vez que você chamar esse função, o compilador chamará o `construtor de cópia` (que você não tem definido), fazendo com que as strings não sejam devidamente alocadas. Uma solução simples é passar o `term` por referência (`T& term`).

---

Outra solução simples para esses problemas é não alocar dinamicamente quando não há necessidade. Por exemplo, na classe você faz:

    // Na classe:
    char* first_name_t; 
    char* second_name_t;
    
    // Em get
    char* first_name = new char[128];
    char* second_name = new char[128];

Você pode simplesmente fazer:

    // Na classe:
    char first_name_t[128]; 
    char second_name_t[128];
    
    // Em get
    char first_name[128];
    char second_name[128];

E limitar que o usuário não informe nomes maiores que 127 caracteres. Com isso você não precisa mais se preocupar em desalocar. A desvantagem de fazer dessa forma é que cada nome sempre ocupará 128 char, ao invés de ocupar apenas o necessário.

---

Imagino que você não possa usar `std::string`, mas esse é um exemplo de porque deve-se usá-la (te pouparia todo esse trabalho). Mas, de qualquer forma, quando se está gerenciando a memória manualmente, recomendasse verificar se a sua classe atende a [Regra dos Três][1] (ou Cinco em C++11). 

  [1]: http://en.wikipedia.org/wiki/Rule_of_three_%28C++_programming%29