Dobre o método de meia-encontro :
Em uma tabela ordenada, compare o valor dos dados a ser pesquisado com o valor do elemento intermediário do intervalo de pesquisa e haverá três situações:
1) Se o valor dos dados a ser encontrado for exatamente igual ao valor do elemento intermediário, coloque de volta o índice do valor do elemento intermediário.
2) Se o valor dos dados a ser pesquisado for menor que o valor do elemento intermediário, use a primeira metade de todo o intervalo de pesquisa como o novo intervalo de pesquisa e execute 1) até que um valor igual seja encontrado.
3) Se o valor dos dados a ser pesquisado for maior que o valor do elemento intermediário, use a segunda metade de todo o intervalo de pesquisa como o novo intervalo de pesquisa e execute 1) até que o valor igual seja encontrado.
4) Se o mesmo valor não puder ser encontrado no final, uma mensagem de erro será retornada.
De acordo com a árvore binária, o valor médio é a raiz da árvore binária, a primeira metade é a subárvore esquerda e a segunda metade é a subárvore direita. O número de pesquisas para o método de pesquisa de meia descoberta é exatamente o número de camadas em que o valor está localizado. Sob igual probabilidade, aproximadamente
log2 (n+1) -1
A cópia do código é a seguinte:
// dados são a matriz a ser pesquisada, x é o valor dos dados a ser pesquisado, BEG é o início do intervalo de pesquisa e o último é o fim do intervalo de pesquisa
// Método não recursivo
int bisearch (int dados [], const int x, int beg, int last)
{
int mid; // posição intermediária
se (implorar> por último)
{
retornar -1;
}
enquanto (Beg <= Last)
{
MID = (BEG + LAST) / 2;
if (x == dados [mid])
{
retornar meio;
}
else if (dados [mid] <x)
{
BEG = MID + 1;
}
caso contrário, se (dados [mid]> x)
{
Último = MID - 1;
}
}
retornar -1;
}
// Método recursivo
int iterbiseearch (int dados [], const int x, int beg, int last)
{
int mid = -1;
MID = (BEG + LAST) / 2;
if (x == dados [mid])
{
retornar meio;
}
else if (x <dados [mid])
{
return iterbisearch (dados, x, implorar, meados - 1);
}
caso contrário, se (x> dados [mid])
{
return iterbisearch (dados, x, médio + 1, último);
}
retornar -1;
}
// Função principal
int _tmain (int argc, _tchar* argv [])
{
int data1 [60] = {0};
int no2search = 45;
cout << "A matriz é:" << 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);
Índice = Iterbisearch (Data1, No2Search, 0, Siz);
cout << "Índice de" << no2search << "é" << index << endl;
getchar ();
retornar 0;
}
A cópia do código é a seguinte:
/**
* Metade para encontrar a posição dos caracteres na matriz (lista ordenada)
* @param matriz a matriz recuperada
* @param x caracteres a serem encontrados
* @RETURNS A posição do personagem na matriz, nenhum resultado é encontrado e retorna -1
*/
function binarySearch (array, x) {
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
Var Midpoint;
var encontrado = false;
while ((Lowpoint <= higpoint) && (! Found)) {
midpoint = math.ceil ((Lowpoint+higpoint)/2);
//console.log(lowPoint+"==="+midpoint+"==="+higPoint);
if (x> Array [Midpoint-1]) {
lowpoint = ponto médio+1;
}
caso contrário, if (x <array [midpoint-1]) {
higpoint = Midpoint-1;
}
else if (x = matriz [Midpoint-1]) {
encontrado = true;
}
}
se (encontrado) {
returnValue = ponto médio;
}
return retornValue;
}
/*var Array2 = [1,2,3,4,5,6,7,8,9,100,109];*/
var Array2 = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
console.log (BininarySearch (Array2, 'C'));