¿Alguien puede enviar el código para la búsqueda binaria en cadenas con clasificación en C ++?

Aqui tienes.

Retazo

#include
#include
#include
#include
#include

typedef std :: vector _string_vector;
typedef _string_vector :: iterator _string_vector_iterator;

// puntero de función de clasificación
typedef void (* _ functor_sort) (_ string_vector &);
typedef bool (* _ functor_binary_search) (_ string_vector_iterator &, _string_vector_iterator &, const std :: string &);

// conjunto de datos init
void _initializeStringCollection (_string_vector & _strings)
{
_strings.push_back (“alksdfasdf”);
_strings.push_back (“sarthak”);
_strings.push_back (“tickoo”);
_strings.push_back (“somethingg”);
_strings.push_back (“foo”);
_strings.push_back (“barra”);
_strings.push_back (“aaaaaaabbbbbbb”);
_strings.push_back (“zzaaaa”);
_strings.push_back (“asHDFKAJSBflkasjbdf”);
_strings.push_back (“qwoeiyqoriyqor”);
_strings.push_back (“some_random_string_2”);
_strings.push_back (“some_random_string”);
_strings.push_back (“some_random_string_3”);
_strings.push_back (“1234569897987”);
_strings.push_back (“alice”);
_strings.push_back (“en”);
_strings.push_back (“país de las maravillas”);
_strings.push_back (“desplomándose”);
_strings.push_back (“la madriguera del conejo”);
}

// Función de clasificación de cadenas: std :: sort over contenedor estándar
void _stdSortMyStrings (_string_vector & _strings)
{
std :: sort (_strings.begin (), _strings.end ());
}

// Función de comparación de cadenas: comparación de cadenas léxicas
int _lexicalCompareMyStrings (std :: string _str1, std :: string _str2)
{
size_t _loopLimit = std :: min (_str1.length (), _str2.length ());
size_t _current_char_index = 0;

while (_current_char_index <_loopLimit)
{
char _lhs = _str1.c_str () [_ current_char_index];
char _rhs = _str2.c_str () [_ current_char_index];
if (_lhs! = _rhs)
return _lhs – _rhs;

++ _ current_char_index;
}

return _str1.length () – _str2.length ();
}

// Función de clasificación de cadenas: usando qsort y comparación léxica de cadenas
void _customSortMyStrings (_string_vector & _strings)
{
std :: qsort (static_cast (& (* _ strings.begin ())),
_strings.size (), sizeof (* _ strings.begin ()),
[] (const void * _str1, const void * _str2) -> int
{
return _lexicalCompareMyStrings (* static_cast (_ str1),
* static_cast (_ str2));
}
);
}

// Función de búsqueda binaria
bool _myBinarySearch (_string_vector_iterator & _start, _string_vector_iterator & _end, const std :: string & _val)
{
size_t _lower_bound = 0, _upper_bound = _end – _start;

while (_lower_bound <= _upper_bound)
{
size_t _mid_pos = static_cast (std :: ceil (std :: div ((_bound_bound + _upper_bound), 2) .quot));
std :: string _current_string = * (_ start + _mid_pos);
if (_current_string == _val)
{
_start + = _mid_pos;
volver verdadero;
}
más if (_lexicalCompareMyStrings (_current_string, _val)> 0)
_upper_bound = _mid_pos – 1;
más if (_lexicalCompareMyStrings (_current_string, _val) <0)
_lower_bound = _mid_pos + 1;
}
falso retorno;
}

int _tmain (int argc, _TCHAR * argv [])
{
// toma una colección de cadenas
_string_vector _randomStrings;

// Esto llamará a la función de clasificación según la que quieras usar
// Realmente no creo que reinventar la rueda para clasificar sea una buena idea dado que la clasificación
// es un lugar común. Sin embargo, le he proporcionado una función de clasificación funcional que utilizo hee. reemplace la función a continuación con _stdSortMyStrings que utilizó la variante STL std :: sort que se ve y funciona mejor.
_functor_sort _string_sorter;
_string_sorter = & _customSortMyStrings; // reemplace esto con & _stdSortMyStrings si desea la variante STL

// Esto llamará a la función de búsqueda según la que quieras usar
// Nuevamente como arriba, STL tiene std :: binary_search que hace el trabajo. Pero he implementado la función para mostrar
// usted el trabajo interno
_functor_binary_search _string_search;

// crea un conjunto de datos aleatorio
_initializeStringCollection (_randomStrings);

// ordenar los datos
_string_sorter (_randomStrings);

// toma alguna entrada del usuario
std :: cout << "Ingrese una cadena para buscar desde la colección ->“;
std :: string _input_string;
std :: cin >> _input_string;

_string_search = & _myBinarySearch; // reemplace esto con & std :: binary_search si desea la variante STL
_string_vector_iterator _start_iter = _randomStrings.begin ();
std :: string _result = _string_search (_start_iter, _randomStrings.end (), _input_string)? “encontrado”: “no encontrado”;
// !!! Nota !!! – mi función incrementa el iterador en el índice donde se encontró la cadena.
// std :: binary_search NO hará esto. Entonces, la siguiente declaración no funcionará.
std :: cout << "Cadena para buscar '" << _input_string << "'" << _result << "en la posición" << static_cast (_start_iter – _randomStrings.begin () + 1) << std: : endl;

devuelve 0;
}

#include “stdafx.h”
#include
#include
usando el espacio de nombres estándar;

// Prototipo de función
void sortArray (cadena [], int);
int binarySearch (cadena [], int, cadena);
const int TAMAÑO = 20;

int main ()
{
// Conjunto definido
const int NUM_NAMES = 20;
nombres de cadena [NUM_NAMES] = {“Collins, Bill”, “Smith, Bart”, “Allen, Jim”,
“Griffin, Jim”, “Stamey, Marty”, “Rose, Geri”,
“Taylor, Terri”, “Johnson, Jill”, “Allison, Jeff”,
“Looney, Joe”, “Wolfe, Bill”, “James, Jean”,
“Weaver, Jim”, “Pore, Bob”, “Rutherford, Greg”,
“Javens, Renee”, “Harrison, Rose”, “Setzer, Cathy”,
“Pike, Gordon”, “Holanda, Beth”};

// Variables
string empName;
int resultados;

// Ordenar primero la matriz
sortArray (nombres, NUM_NAMES);

// Solicitar la entrada del usuario para ingresar el nombre de un empleado
cout << "Ingrese el nombre de un empleado:";
getline (cin, empName);

// Buscar nombre
resultados = binarySearch (nombres, NUM_NAMES, empName);

// Si los resultados contienen -1, no se encontró el nombre.
if (resultados == -1)
cout << "Ese nombre no existe en la matriz. \ n";
más
{
// De lo contrario, los resultados contienen el subíndice de
// el ID de empleado especificado en la matriz.
cout << "Ese nombre se encuentra en el elemento" << resultados;
cout << "en la matriz. \ n";
}

sistema (“PAUSA”);

devuelve 0;
}

// ************************************************ **************
// Definición de la función sortArray. * *
// Esta función realiza una selección de orden ascendente en *
// matriz. tamaño es el número de elementos en la matriz. * *
// ************************************************ **************
void sortArray (nombres de cadena [], tamaño int)
{
int startScan, minIndex;
string minValue;

for (startScan = 0; startScan <(tamaño - 1); startScan ++)
{
minIndex = startScan;
minValue = nombres [startScan];
for (int index = startScan + 1; index {
if (nombres [índice] {
minValue = nombres [índice];
minIndex = index;
}
}
nombres [minIndex] = nombres [startScan];
nombres [startScan] = minValue;
}
}

// ************************************************ ***************
// La función binarySearch realiza una búsqueda binaria en un *
// matriz entera. matriz, que tiene un máximo de elementos de tamaño, *
// se busca el número almacenado en el valor. Si el número es *
// encontrado, se devuelve su subíndice de matriz. De lo contrario, -1 es *
// devuelto indicando que el valor no estaba en la matriz. * *
// ************************************************ ***************
int binarySearch (nombres de cadena [], tamaño int, valor de cadena)
{
int first = 0, // primer elemento de la matriz
last = size – 1, // Último elemento de matriz
medio, // punto medio de búsqueda
posición = -1; // Posición del valor de búsqueda
bool encontrado = falso; // bandera

while (! encontrado && first <= last)
{
medio = (primero + último) / 2; // Calcular punto medio
if (names [middle] == value) // Si el valor se encuentra a mediados
{
encontrado = verdadero;
posición = medio;
}
sino if (names [middle]> value) // Si el valor está en la mitad inferior
último = medio – 1;
más
primero = medio + 1; // Si el valor está en la mitad superior
}
posición de retorno;
}