Doble el método de la medias de encontrar :
En una tabla ordenada, compare el valor de datos que se buscará con el valor del elemento intermedio del rango de búsqueda, y habrá tres situaciones:
1) Si el valor de los datos que se encuentra es exactamente igual al valor del elemento intermedio, vuelva a colocar el índice del valor del elemento intermedio.
2) Si el valor de los datos a buscar es menor que el valor del elemento intermedio, use la primera mitad del rango de búsqueda completo como el nuevo rango de búsqueda y ejecute 1) hasta que se encuentre un valor igual.
3) Si el valor de los datos a buscar es mayor que el valor del elemento intermedio, use la segunda mitad del rango de búsqueda completo como el nuevo rango de búsqueda, y ejecute 1) hasta que se encuentre el valor igual.
4) Si el mismo valor no se puede encontrar al final, se devolverá un mensaje de error.
Según el árbol binario, el valor medio es la raíz del árbol binario, la primera mitad es el subárbol izquierdo, y la segunda mitad es el subárbol derecho. El número de búsquedas para el método de búsqueda de media búsqueda es exactamente el número de capas donde se encuentra el valor. Bajo igual probabilidad, aproximadamente
log2 (n+1) -1
La copia del código es la siguiente:
// Los datos son la matriz a buscar, x es el valor de datos a buscar, Beg es el comienzo del rango de búsqueda y el último es el final del rango de búsqueda
// método no recursivo
int bISearch (int data [], const int x, int beg, int último)
{
int mid; // posición media
if (beg> ort)
{
regreso -1;
}
Mientras (Beg <= Last)
{
Mid = (Beg + Last) / 2;
if (x == datos [Mid])
{
regresar medio;
}
else if (data [Mid] <x)
{
Beg = Mid + 1;
}
else if (data [mid]> x)
{
último = Mid - 1;
}
}
regreso -1;
}
// método recursivo
int iterbisearch (int data [], const int x, int beg, int último)
{
int mid = -1;
Mid = (Beg + Last) / 2;
if (x == datos [Mid])
{
regresar medio;
}
else if (x <data [mid])
{
return iterbisearch (datos, x, beg, mediano - 1);
}
else if (x> data [Mid])
{
return iterbisearch (datos, x, mediano + 1, último);
}
regreso -1;
}
// función principal
int _tmain (int argc, _tchar* argv [])
{
int data1 [60] = {0};
int no2Search = 45;
cout << "La matriz es:" << endl;
int siz = sizeof (data1)/sizeof (int);
para (int i = 0; i <siz; i ++)
{
data1 [i] = i;
cout << data1 [i] << "";
}
cout << endl;
int index = -1;
// index = bISearch (data1, no2Search, 0, siz);
index = iterbisearch (data1, NO2Search, 0, Siz);
cout << "índice de" << no2Search << "es" << índice << endl;
getchar ();
regresar 0;
}
La copia del código es la siguiente:
/**
* La mitad para encontrar la posición de los caracteres en la matriz (lista ordenada)
* @param matriz la matriz recuperada
* @param x personajes a encontrar
* @returns La posición del personaje en la matriz, no se encuentran resultados y return -1
*/
function binarySearch (Array, x) {
var LowPoint = 1;
var higpoint = array.length;
var returnValue = -1;
Var punto medio;
var encontrado = falso;
while ((LowPoint <= HigPoint) && (! Found)) {
Midpoint = Math.ceil ((LowPoint+HigPoint)/2);
//console.log(lowpoint+"===="+MidPoint+"===="+HigPoint);
if (x> array [midpoint-1]) {
LowPoint = punto medio+1;
}
else if (x <array [midpoint-1]) {
higpoint = punto medio-1;
}
else if (x = array [midpoint-1]) {
encontrado = verdadero;
}
}
if (encontrado) {
returnValue = punto medio;
}
return returnValue;
}
/*var array2 = [1,2,3,4,5,6,7,8,9,100,109];*/
var array2 = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
console.log (binarySearch (array2, 'c'));