Suponhamos que o dicionário tem 1000 páginas. Uma abordagem comum é abrirmos o dicionário no meio, 500ª página. Digamos que calhamos numa página cujas palavras começam por "L". Isto significa que "inócuo" tem de estar para a esquerda no dicionário pois "I" vem antes do "L".
Assim, podemos repetir o processo mas considerando apenas a primeira metade das páginas. Desta vez vamos à 250ª página e suponham que esta página tem palavras começam por "F". Deste modo, sabemos que "inócuo" tem de estar para a direita - iríamos para a 375ª página a seguir. Após repetir o processo, vamos encontrar (eventualmente) uma página referente à letra "I". De seguida, continuamos com a 2ª letra da palavra a procurar - "n" em "inócuo" - e assim sucessivamente até encontrar a palavra.
|
A procura no dicionário é provavelmente intuitiva para toda a gente e pode até parecer estranho sistematizar este processo. No entanto, é esta sistematização que nos permite aplicar este método num programa. No exemplo anterior, começamos com um dicionário de 1000 páginas e fomos reduzindo o intervalo de páginas a procurar (espaço de pesquisa) para metade em cada iteração: 1000 -> 500 -> 250 -> 125 -> 63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1. Reparem que necessitamos de procurar apenas 10 páginas em vez de 1000 para encontrar a palavra.
Este método tem o nome de Pesquisa Binária (Binary Search no TopCoder). Visto que reduzimos o espaço de pesquisa para metade em cada iteração, a complexidade temporal deste método é O(log N): log2(1000) ~ 10. O único requisito da pesquisa binária é que exista uma ordem no input, seja ele um dicionário (palavras ordenadas alfabeticamente), um array de números ordenados ou outra.
Implementação em C++ da pesquisa de um número num array ordenado de forma crescente (retorna o índice no array:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // Se existirem valores repetidos iguais a "valor", retorna um qualquer. int PesquisaBinaria(int* valores, int n, int valor) { int esq = 0, dir = n-1; while (esq <= dir) { int mid = (esq + dir) / 2; if (valores[mid] == valor) { // encontrou! return mid; } else if (valores[mid] < valor) { // está na parte direita esq = mid+1; } else { // está na parte esquerda dir = mid-1; } } return -1; // inexistente } |
2 problemas relacionados já referidos em posts anteriores são:
- Procurar o menor número maior ou igual a um valor dado - função lower_bound em C++
- Procurar o menor número maior do que um valor dado - função upper_bound em C++
Este problema pode ser abordado com pesquisa binária. A diferença para a pesquisa binária tradicional é que não procuramos um número especifico. Não terminamos a pesquisa precocemente, mas encurtamos o espaço de pesquisa até 1 elemento.
Notem que a diferença entre as duas funções é apenas uma condição com < e outra com <=. Caso não exista solução, as funções devolvem n, o número de elementos do array.
No caso do LowerBound, se existirem múltiplos valores iguais ao valor a procurar, retorna o menor índice no array com esse valor.
No caso do LowerBound, se existirem múltiplos valores iguais ao valor a procurar, retorna o menor índice no array com esse valor.
1 2 3 4 5 6 7 8 9 10 11 12 13 | // Procura o menor número maior ou igual ao valor dado num array ordenado int LowerBound(int* valores, int n, int valor) { int esq = 0, dir = n-1; while (esq <= dir) { int mid = (esq + dir) / 2; if (valores[mid] < valor) { // está na parte direita esq = mid+1; } else { dir = mid-1; } } return esq; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 | // Procura o menor número maior do que o valor dado num array ordenado int UpperBound(int* valores, int n, int valor) { int esq = 0, dir = n-1; while (esq <= dir) { int mid = (esq + dir) / 2; if (valores[mid] <= valor) { // está na parte direita esq = mid+1; } else { dir = mid-1; } } return esq; } |
Existem outras aplicações da pesquisa binária. Por exemplo: como encontrar a raiz quadrada de um número sem recorrer a funções standard?
Steel Tritanium White Domus of the Roman Empire
ResponderEliminarSteel Tritanium White Domus of the titanium dioxide sunscreen Roman Empire. titanium price per ounce In Roman Art, titanium easy flux 125 amp welder Steel Tritanium White Domus of the titanium oxide formula Roman titanium tent stove Empire.
imp source realistic sex dolls,sex dolls,wholesale sex toys,sex toys,dog dildo,sex toys,dildos,love dolls,sex toys you can try these out
ResponderEliminarhd517 jordan 4 fire red,jordan 4 military black,aj 1 unc,yeezy 350 beluga,jordan 1 royal toe,jordan 4 unc,yeezy 350 v2,aj 1 chicago,aj 1 travis scott
ResponderEliminar