Algoritmo de pesquisa binária - Binary search algorithm

Algoritmo de busca binária
Binary Search Depiction.svg
Visualização do algoritmo de busca binária onde 7 é o valor alvo
Classe Algoritmo de busca
Estrutura de dados Variedade
Desempenho de pior caso O (log n )
Melhor caso de desempenho O (1)
Desempenho médio O (log n )
Pior caso de complexidade de espaço O (1)

Na ciência da computação , a pesquisa binária , também conhecida como pesquisa de meio intervalo , pesquisa logarítmica ou divisão binária , é um algoritmo de pesquisa que encontra a posição de um valor de destino em uma matriz classificada . A pesquisa binária compara o valor de destino com o elemento do meio da matriz. Se não forem iguais, a metade em que o alvo não pode estar é eliminada e a busca continua na metade restante, novamente tomando o elemento do meio para comparar com o valor alvo, e repetindo até que o valor alvo seja encontrado. Se a pesquisa terminar com a metade restante vazia, o alvo não está na matriz.

A pesquisa binária é executada em tempo logarítmico no pior caso , fazendo comparações, onde é o número de elementos na matriz. A pesquisa binária é mais rápida do que a pesquisa linear, exceto para pequenas matrizes. No entanto, a matriz deve ser classificada primeiro para poder aplicar a pesquisa binária. Existem estruturas de dados especializadas projetadas para pesquisa rápida, como tabelas hash , que podem ser pesquisadas com mais eficiência do que a pesquisa binária. No entanto, a pesquisa binária pode ser usada para resolver uma gama mais ampla de problemas, como encontrar o próximo menor ou o próximo maior elemento na matriz em relação ao destino, mesmo se estiver ausente da matriz.

Existem inúmeras variações de pesquisa binária. Em particular, a cascata fracionária acelera as pesquisas binárias para o mesmo valor em várias matrizes. A cascata fracionária resolve com eficiência uma série de problemas de pesquisa em geometria computacional e em vários outros campos. A pesquisa exponencial estende a pesquisa binária a listas ilimitadas. A árvore de pesquisa binária e as estruturas de dados da árvore B são baseadas na pesquisa binária.

Algoritmo

A pesquisa binária funciona em matrizes classificadas. A pesquisa binária começa comparando um elemento no meio da matriz com o valor de destino. Se o valor de destino corresponder ao elemento, sua posição na matriz será retornada. Se o valor de destino for menor que o elemento, a pesquisa continua na metade inferior da matriz. Se o valor de destino for maior que o elemento, a pesquisa continua na metade superior da matriz. Fazendo isso, o algoritmo elimina a metade na qual o valor de destino não pode estar em cada iteração.

Procedimento

Dada uma matriz de elementos com valores ou registros classificados de forma que , e o valor alvo , a seguinte sub-rotina usa a pesquisa binária para encontrar o índice de in .

  1. Defina para e para .
  2. Se , a pesquisa termina como malsucedida.
  3. Defina (a posição do elemento do meio) para o piso de , que é o maior inteiro menor ou igual a .
  4. Se , defina como e vá para a etapa 2.
  5. Se , defina como e vá para a etapa 2.
  6. Agora , a pesquisa está concluída; voltar .

Este procedimento iterativo acompanha os limites da pesquisa com as duas variáveis e . O procedimento pode ser expresso em pseudocódigo como segue, onde os nomes e tipos de variáveis ​​permanecem os mesmos que acima, é a função de piso e se refere a um valor específico que indica o fracasso da pesquisa. floorunsuccessful

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

Alternativamente, o algoritmo pode assumir o teto de . Isso pode alterar o resultado se o valor alvo aparecer mais de uma vez na matriz.

Procedimento alternativo

No procedimento acima, o algoritmo verifica se o elemento do meio ( ) é igual ao destino ( ) em cada iteração. Algumas implementações deixam de fora essa verificação durante cada iteração. O algoritmo executaria essa verificação apenas quando um elemento fosse deixado (quando ). Isso resulta em um loop de comparação mais rápido, pois uma comparação é eliminada por iteração. No entanto, requer mais uma iteração em média.

Hermann Bottenbruch publicou a primeira implementação para omitir essa verificação em 1962.

  1. Defina para e para .
  2. Enquanto ,
    1. Defina (a posição do elemento do meio) para o teto de , que é o menor número inteiro maior ou igual a .
    2. Se , defina como .
    3. Else ,; definido como .
  3. Agora , a pesquisa está concluída. Se , volte . Caso contrário, a pesquisa termina como malsucedida.

Onde ceilestá a função de teto, o pseudocódigo para esta versão é:

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

Elementos duplicados

O procedimento pode retornar qualquer índice cujo elemento seja igual ao valor de destino, mesmo se houver elementos duplicados na matriz. Por exemplo, se a matriz a ser pesquisada era e o destino era , então seria correto que o algoritmo retornasse o 4º (índice 3) ou o 5º (índice 4) elemento. O procedimento regular retornaria o 4º elemento (índice 3) neste caso. Nem sempre retorna a primeira duplicata (considere qual ainda retorna o 4º elemento). No entanto, às vezes é necessário localizar o elemento mais à esquerda ou o elemento mais à direita para um valor de destino que está duplicado na matriz. No exemplo acima, o 4º elemento é o elemento mais à esquerda do valor 4, enquanto o 5º elemento é o elemento mais à direita do valor 4. O procedimento alternativo acima sempre retornará o índice do elemento mais à direita se tal elemento existir.

Procedimento para encontrar o elemento mais à esquerda

Para encontrar o elemento mais à esquerda, o seguinte procedimento pode ser usado:

  1. Defina para e para .
  2. Enquanto ,
    1. Defina (a posição do elemento do meio) para o piso de , que é o maior inteiro menor ou igual a .
    2. Se , defina como .
    3. Else ,; definido como .
  3. Retorno .

Se e , então é o elemento mais à esquerda igual . Mesmo se não estiver na matriz, é a classificação de na matriz ou o número de elementos na matriz que são menores que .

Onde floorestá a função de piso, o pseudocódigo para esta versão é:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Procedimento para encontrar o elemento mais à direita

Para encontrar o elemento mais à direita, o seguinte procedimento pode ser usado:

  1. Defina para e para .
  2. Enquanto ,
    1. Defina (a posição do elemento do meio) para o piso de , que é o maior inteiro menor ou igual a .
    2. Se , defina como .
    3. Else ,; definido como .
  3. Retorno .

Se e , então é o elemento mais à direita que é igual . Mesmo que não esteja na matriz, o número de elementos na matriz é maior que .

Onde floorestá a função de piso, o pseudocódigo para esta versão é:

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Combinações aproximadas

A pesquisa binária pode ser adaptada para calcular correspondências aproximadas. No exemplo acima, a classificação, o predecessor, o sucessor e o vizinho mais próximo são mostrados para o valor de destino , que não está na matriz.

O procedimento acima executa apenas correspondências exatas , encontrando a posição de um valor alvo. No entanto, é trivial estender a pesquisa binária para realizar correspondências aproximadas porque a pesquisa binária opera em matrizes classificadas. Por exemplo, a pesquisa binária pode ser usada para calcular, para um determinado valor, sua classificação (o número de elementos menores), predecessor (próximo elemento menor), sucessor (próximo maior elemento) e vizinho mais próximo . Consultas de intervalo buscando o número de elementos entre dois valores podem ser realizadas com duas consultas de classificação.

  • As consultas de classificação podem ser realizadas com o procedimento para localizar o elemento mais à esquerda . O número de elementos menor que o valor de destino é retornado pelo procedimento.
  • As consultas predecessoras podem ser realizadas com consultas de classificação. Se a classificação do valor de destino for , seu predecessor será  .
  • Para consultas de sucessores, o procedimento para localizar o elemento mais à direita pode ser usado. Se o resultado da execução do procedimento para o valor de destino for , então o sucessor do valor de destino é  .
  • O vizinho mais próximo do valor de destino é seu predecessor ou sucessor, o que estiver mais próximo.
  • As consultas de intervalo também são diretas. Uma vez que as classificações dos dois valores são conhecidas, o número de elementos maior ou igual ao primeiro valor e menor que o segundo é a diferença das duas classificações. Essa contagem pode ser ajustada para cima ou para baixo em um, de acordo com se os terminais do intervalo devem ser considerados parte do intervalo e se a matriz contém entradas correspondentes a esses terminais.

atuação

Uma árvore que representa a pesquisa binária. A matriz que está sendo pesquisada aqui é , e o valor de destino é .
O pior caso é alcançado quando a pesquisa atinge o nível mais profundo da árvore, enquanto o melhor caso é alcançado quando o valor alvo é o elemento do meio.

Em termos de número de comparações, o desempenho da pesquisa binária pode ser analisado visualizando a execução do procedimento em uma árvore binária. O nó raiz da árvore é o elemento do meio da matriz. O elemento do meio da metade inferior é o nó filho esquerdo da raiz e o elemento do meio da metade superior é o nó filho direito da raiz. O resto da árvore é construído de maneira semelhante. Começando no nó raiz, as subárvores esquerda ou direita são percorridas dependendo se o valor de destino é menor ou maior do que o nó em consideração.

No pior caso, a pesquisa binária faz iterações do loop de comparação, onde a notação denota a função de base que produz o maior inteiro menor ou igual ao argumento e é o logaritmo binário . Isso ocorre porque o pior caso é alcançado quando a pesquisa atinge o nível mais profundo da árvore, e sempre há níveis na árvore para qualquer pesquisa binária.

O pior caso também pode ser alcançado quando o elemento de destino não está na matriz. Se for um a menos do que uma potência de dois, esse será sempre o caso. Caso contrário, a pesquisa pode realizar iterações se a pesquisa atingir o nível mais profundo da árvore. No entanto, ele pode fazer iterações, o que é um a menos que o pior caso, se a pesquisa terminar no segundo nível mais profundo da árvore.

Em média, supondo que cada elemento tenha a mesma probabilidade de ser pesquisado, a pesquisa binária faz iterações quando o elemento de destino está na matriz. Isso é aproximadamente igual a iterações. Quando o elemento de destino não está na matriz, a pesquisa binária faz iterações em média, supondo que o intervalo entre os elementos externos seja igualmente provável de ser pesquisado.

No melhor caso, onde o valor de destino é o elemento do meio da matriz, sua posição é retornada após uma iteração.

Em termos de iterações, nenhum algoritmo de pesquisa que funcione apenas comparando elementos pode exibir melhor desempenho médio e de pior caso do que a pesquisa binária. A árvore de comparação que representa a pesquisa binária tem o menor número possível de níveis, pois cada nível acima do nível mais baixo da árvore é preenchido completamente. Caso contrário, o algoritmo de busca pode eliminar poucos elementos em uma iteração, aumentando o número de iterações necessárias na média e no pior caso. Esse é o caso de outros algoritmos de pesquisa baseados em comparações, pois embora possam funcionar mais rápido em alguns valores de destino, o desempenho médio de todos os elementos é pior do que a pesquisa binária. Ao dividir a matriz pela metade, a pesquisa binária garante que o tamanho de ambas as submatrizes seja o mais semelhante possível.

Complexidade do espaço

A pesquisa binária requer três ponteiros para elementos, que podem ser índices de array ou ponteiros para locais de memória, independentemente do tamanho do array. Portanto, a complexidade espacial da pesquisa binária está na palavra RAM model of computation.

Derivação do caso médio

O número médio de iterações realizadas pela pesquisa binária depende da probabilidade de cada elemento ser pesquisado. O caso médio é diferente para pesquisas bem-sucedidas e pesquisas malsucedidas. Será assumido que cada elemento tem a mesma probabilidade de ser pesquisado para pesquisas bem-sucedidas. Para buscas malsucedidas, será assumido que os intervalos entre os elementos externos são igualmente prováveis ​​de serem procurados. O caso médio de pesquisas bem-sucedidas é o número de iterações necessárias para pesquisar cada elemento exatamente uma vez, dividido pelo número de elementos. O caso médio de pesquisas malsucedidas é o número de iterações necessárias para pesquisar um elemento em cada intervalo exatamente uma vez, dividido pelos intervalos.

Buscas bem sucedidas

Na representação da árvore binária, uma pesquisa bem-sucedida pode ser representada por um caminho da raiz até o nó de destino, chamado de caminho interno . O comprimento de um caminho é o número de arestas (conexões entre nós) pelas quais o caminho passa. O número de iterações realizadas por uma pesquisa, dado que o caminho correspondente tem comprimento , está contando a iteração inicial. O comprimento do caminho interno é a soma dos comprimentos de todos os caminhos internos exclusivos. Como há apenas um caminho da raiz para qualquer nó único, cada caminho interno representa uma busca por um elemento específico. Se houver elementos, que é um número inteiro positivo, e o comprimento do caminho interno é , então o número médio de iterações para uma pesquisa bem-sucedida , com uma iteração adicionada para contar a iteração inicial.

Uma vez que a pesquisa binária é o algoritmo ideal para pesquisar com comparações, este problema é reduzido ao cálculo do comprimento do caminho interno mínimo de todas as árvores binárias com nós, que é igual a:

Por exemplo, em uma matriz de 7 elementos, a raiz requer uma iteração, os dois elementos abaixo da raiz requerem duas iterações e os quatro elementos abaixo requerem três iterações. Nesse caso, o comprimento do caminho interno é:

O número médio de iterações seria baseado na equação para o caso médio. A soma de pode ser simplificada para:

Substituindo a equação por na equação de :

Para inteiros , isso é equivalente à equação para o caso médio em uma pesquisa bem-sucedida especificada acima.

Pesquisas sem sucesso

As pesquisas malsucedidas podem ser representadas aumentando a árvore com nós externos , que formam uma árvore binária estendida . Se um nó interno, ou um nó presente na árvore, tiver menos de dois nós filhos, então nós filhos adicionais, chamados de nós externos, serão adicionados para que cada nó interno tenha dois filhos. Ao fazer isso, uma pesquisa malsucedida pode ser representada como um caminho para um nó externo, cujo pai é o único elemento que permanece durante a última iteração. Um caminho externo é um caminho da raiz para um nó externo. O comprimento do caminho externo é a soma dos comprimentos de todos os caminhos externos exclusivos. Se houver elementos, que é um número inteiro positivo, e o comprimento do caminho externo é , então o número médio de iterações para uma pesquisa malsucedida , com uma iteração adicionada para contar a iteração inicial. O comprimento do caminho externo é dividido por em vez de porque existem caminhos externos, representando os intervalos entre e fora dos elementos da matriz.

Esse problema pode ser reduzido da mesma forma para determinar o comprimento mínimo do caminho externo de todas as árvores binárias com nós. Para todas as árvores binárias, o comprimento do caminho externo é igual ao comprimento do caminho interno mais . Substituindo a equação por :

Substituindo a equação por na equação de , o caso médio para pesquisas malsucedidas pode ser determinado:

Desempenho de procedimento alternativo

Cada iteração do procedimento de busca binária definido acima faz uma ou duas comparações, verificando se o elemento do meio é igual ao destino em cada iteração. Assumindo que cada elemento tem a mesma probabilidade de ser pesquisado, cada iteração faz 1,5 comparações em média. Uma variação do algoritmo verifica se o elemento do meio é igual ao alvo no final da pesquisa. Em média, isso elimina meia comparação de cada iteração. Isso reduz um pouco o tempo gasto por iteração na maioria dos computadores. No entanto, garante que a pesquisa leva o número máximo de iterações, em média adicionando uma iteração à pesquisa. Como o loop de comparação é executado apenas algumas vezes no pior caso, o ligeiro aumento na eficiência por iteração não compensa a iteração extra para todos, mas muito grande .

Tempo de execução e uso de cache

Ao analisar o desempenho da pesquisa binária, outra consideração é o tempo necessário para comparar dois elementos. Para inteiros e strings, o tempo necessário aumenta linearmente conforme o comprimento da codificação (geralmente o número de bits ) dos elementos aumenta. Por exemplo, comparar um par de inteiros não assinados de 64 bits exigiria a comparação de até o dobro dos bits da comparação de um par de inteiros não assinados de 32 bits. O pior caso é alcançado quando os inteiros são iguais. Isso pode ser significativo quando os comprimentos de codificação dos elementos são grandes, como no caso de tipos inteiros grandes ou strings longas, o que torna caro a comparação de elementos. Além disso, comparar valores de ponto flutuante (a representação digital mais comum de números reais ) costuma ser mais caro do que comparar inteiros ou strings curtas.

Na maioria das arquiteturas de computador, o processador tem um cache de hardware separado da RAM . Como estão localizados no próprio processador, os caches são muito mais rápidos de acessar, mas geralmente armazenam muito menos dados do que a RAM. Portanto, a maioria dos processadores armazena locais de memória que foram acessados ​​recentemente, junto com locais de memória próximos a eles. Por exemplo, quando um elemento da matriz é acessado, o próprio elemento pode ser armazenado junto com os elementos que são armazenados próximos a ele na RAM, tornando mais rápido acessar sequencialmente os elementos da matriz que estão próximos no índice uns dos outros ( localidade de referência ) . Em uma matriz classificada, a pesquisa binária pode saltar para locais de memória distantes se a matriz for grande, ao contrário dos algoritmos (como pesquisa linear e sondagem linear em tabelas hash ) que acessam elementos em sequência. Isso aumenta ligeiramente o tempo de execução da pesquisa binária para grandes arrays na maioria dos sistemas.

Pesquisa binária versus outros esquemas

Matrizes classificadas com pesquisa binária são uma solução muito ineficiente quando as operações de inserção e exclusão são intercaladas com a recuperação, levando tempo para cada operação. Além disso, os arrays classificados podem complicar o uso da memória, especialmente quando os elementos são frequentemente inseridos no array. Existem outras estruturas de dados que suportam inserção e exclusão muito mais eficientes. A pesquisa binária pode ser usada para executar correspondência exata e associação de conjunto (determinando se um valor de destino está em uma coleção de valores). Existem estruturas de dados que suportam correspondência exata mais rápida e associação de conjuntos. No entanto, ao contrário de muitos outros esquemas de pesquisa, a pesquisa binária pode ser usada para correspondência aproximada eficiente, geralmente realizando tais correspondências no tempo, independentemente do tipo ou estrutura dos próprios valores. Além disso, existem algumas operações, como localizar o menor e o maior elemento, que podem ser realizadas de forma eficiente em uma matriz classificada.

Pesquisa linear

A pesquisa linear é um algoritmo de pesquisa simples que verifica cada registro até encontrar o valor de destino. A pesquisa linear pode ser feita em uma lista vinculada, o que permite uma inserção e exclusão mais rápidas do que uma matriz. A pesquisa binária é mais rápida do que a pesquisa linear para matrizes classificadas, exceto se a matriz for curta, embora a matriz precise ser classificada de antemão. Todos os algoritmos de classificação baseados na comparação de elementos, como quicksort e merge sort , requerem pelo menos comparações no pior caso. Ao contrário da pesquisa linear, a pesquisa binária pode ser usada para uma correspondência aproximada eficiente. Existem operações, como encontrar o menor e o maior elemento, que podem ser feitas com eficiência em uma matriz classificada, mas não em uma matriz não classificada.

Arvores

Árvores de pesquisa binárias são pesquisadas usando um algoritmo semelhante à pesquisa binária.

Uma árvore de pesquisa binária é uma estrutura de dados de árvore binária que funciona com base no princípio da pesquisa binária. Os registros da árvore são organizados em ordem de classificação, e cada registro na árvore pode ser pesquisado usando um algoritmo semelhante à pesquisa binária, levando em média um tempo logarítmico. A inserção e exclusão também requerem, em média, tempo logarítmico nas árvores binárias de pesquisa. Isso pode ser mais rápido do que a inserção e exclusão de tempo linear de matrizes classificadas, e as árvores binárias retêm a capacidade de realizar todas as operações possíveis em uma matriz classificada, incluindo intervalo e consultas aproximadas.

No entanto, a pesquisa binária é geralmente mais eficiente para pesquisar, pois as árvores de pesquisa binária provavelmente serão balanceadas de maneira imperfeita, resultando em um desempenho um pouco pior do que a pesquisa binária. Isso se aplica até mesmo a árvores de pesquisa binárias balanceadas , árvores de pesquisa binárias que equilibram seus próprios nós, porque raramente produzem a árvore com o menor número possível de níveis. Exceto para árvores de pesquisa binárias balanceadas, a árvore pode estar gravemente desequilibrada com poucos nós internos com dois filhos, resultando em comparações de aproximação de tempo de pesquisa médio e de pior caso . As árvores de pesquisa binárias ocupam mais espaço do que as matrizes classificadas.

As árvores de pesquisa binárias se prestam a pesquisas rápidas na memória externa armazenada em discos rígidos, pois as árvores de pesquisa binária podem ser estruturadas de forma eficiente em sistemas de arquivos. A árvore B generaliza esse método de organização em árvore. Árvores B são freqüentemente usadas para organizar armazenamento de longo prazo, como bancos de dados e sistemas de arquivos .

Hashing

Para implementar matrizes associativas , tabelas hash , uma estrutura de dados que mapeia chaves para registros usando uma função hash , geralmente são mais rápidas do que a pesquisa binária em uma matriz classificada de registros. A maioria das implementações de hash table requer apenas tempo constante amortizado em média. No entanto, o hash não é útil para correspondências aproximadas, como calcular a próxima menor, a próxima maior e a chave mais próxima, pois a única informação fornecida em uma pesquisa com falha é que o destino não está presente em nenhum registro. A pesquisa binária é ideal para tais correspondências, realizando-as em tempo logarítmico. A pesquisa binária também oferece suporte a correspondências aproximadas. Algumas operações, como localizar o menor e o maior elemento, podem ser feitas com eficiência em matrizes classificadas, mas não em tabelas de hash.

Definir algoritmos de adesão

Um problema relacionado à pesquisa é a associação definida . Qualquer algoritmo que faça pesquisa, como pesquisa binária, também pode ser usado para associação de conjunto. Existem outros algoritmos que são mais especificamente adequados para associação a conjuntos. Uma matriz de bits é a mais simples, útil quando o intervalo de chaves é limitado. Ele armazena compactamente uma coleção de bits , com cada bit representando uma única chave dentro do intervalo de chaves. As matrizes de bits são muito rápidas, exigindo apenas tempo. O tipo Judy1 de array Judy lida com chaves de 64 bits com eficiência.

Para obter resultados aproximados, os filtros Bloom , outra estrutura de dados probabilística baseada em hash, armazenam um conjunto de chaves codificando as chaves usando uma matriz de bits e várias funções hash. Os filtros Bloom são muito mais eficientes em termos de espaço do que os arrays de bits na maioria dos casos e não muito mais lentos: com funções hash, as consultas de associação requerem apenas tempo. No entanto, os filtros Bloom sofrem de falsos positivos .

Outras estruturas de dados

Existem estruturas de dados que podem melhorar a pesquisa binária em alguns casos, tanto para pesquisa quanto para outras operações disponíveis para matrizes classificadas. Por exemplo, pesquisas, correspondências aproximadas e as operações disponíveis para matrizes classificadas podem ser realizadas com mais eficiência do que a pesquisa binária em estruturas de dados especializadas, como árvores de van Emde Boas , árvores de fusão , tentativas e matrizes de bits . Essas estruturas de dados especializadas são geralmente mais rápidas porque aproveitam as propriedades das chaves com um determinado atributo (geralmente chaves que são inteiros pequenos) e, portanto, consumirão tempo ou espaço para chaves que não possuem esse atributo. Desde que as chaves possam ser solicitadas, essas operações sempre podem ser feitas de maneira eficiente em uma matriz classificada, independentemente das chaves. Algumas estruturas, como arrays de Judy, usam uma combinação de abordagens para atenuar isso, mantendo a eficiência e a capacidade de realizar correspondência aproximada.

Variações

Pesquisa binária uniforme

A pesquisa binária uniforme armazena a diferença entre o atual e os dois próximos elementos intermediários possíveis, em vez de limites específicos.

A pesquisa binária uniforme armazena, em vez dos limites inferior e superior, a diferença no índice do elemento do meio da iteração atual para a próxima iteração. Uma tabela de pesquisa contendo as diferenças é calculada de antemão. Por exemplo, se a matriz a ser pesquisada for [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] , o elemento do meio ( ) seria 6 . Nesse caso, o elemento do meio do subarray esquerdo ( [1, 2, 3, 4, 5] ) é 3 e o elemento do meio do subarray direito ( [7, 8, 9, 10, 11] ) é 9 . A pesquisa binária uniforme armazenaria o valor de 3, pois ambos os índices diferem de 6 por esse mesmo valor. Para reduzir o espaço de pesquisa, o algoritmo adiciona ou subtrai essa alteração do índice do elemento do meio. A pesquisa binária uniforme pode ser mais rápida em sistemas onde é ineficiente calcular o ponto médio, como em computadores decimais .

Pesquisa exponencial

Visualização da pesquisa exponencial encontrando o limite superior para a pesquisa binária subsequente

A pesquisa exponencial estende a pesquisa binária a listas ilimitadas. Ele começa encontrando o primeiro elemento com um índice que é uma potência de dois e maior que o valor de destino. Posteriormente, ele define esse índice como o limite superior e muda para a pesquisa binária. Uma pesquisa leva iterações antes do início da pesquisa binária e no máximo iterações da pesquisa binária, onde é a posição do valor de destino. A pesquisa exponencial funciona em listas limitadas, mas se torna uma melhoria em relação à pesquisa binária apenas se o valor de destino estiver próximo ao início da matriz.

Pesquisa de interpolação

Visualização da pesquisa de interpolação usando interpolação linear. Nesse caso, nenhuma pesquisa é necessária porque a estimativa da localização do alvo dentro da matriz está correta. Outras implementações podem especificar outra função para estimar a localização do alvo.

Em vez de calcular o ponto médio, a busca de interpolação estima a posição do valor alvo, levando em consideração os elementos mais baixos e mais altos da matriz, bem como o comprimento da matriz. Ele funciona com base no fato de que o ponto médio não é a melhor estimativa em muitos casos. Por exemplo, se o valor de destino estiver próximo ao elemento mais alto da matriz, é provável que ele esteja localizado próximo ao final da matriz.

Uma função de interpolação comum é a interpolação linear . Se for a matriz, forem os limites inferior e superior, respectivamente, e for o destino, estima-se que o destino esteja entre e . Quando a interpolação linear é usada e a distribuição dos elementos da matriz é uniforme ou quase uniforme, a pesquisa de interpolação faz comparações.

Na prática, a pesquisa de interpolação é mais lenta do que a pesquisa binária para pequenos arrays, pois a pesquisa de interpolação requer computação extra. Sua complexidade de tempo cresce mais lentamente do que a pesquisa binária, mas isso apenas compensa a computação extra para grandes matrizes.

Cascata fracionária

Em cascata fracionária , cada array possui ponteiros para cada segundo elemento de outro array, portanto, apenas uma pesquisa binária deve ser realizada para pesquisar todos os arrays.

O cascateamento fracionário é uma técnica que acelera pesquisas binárias para o mesmo elemento em várias matrizes classificadas. Pesquisar cada array separadamente requer tempo, onde está o número de arrays. O cascateamento fracionário reduz isso ao armazenamento de informações específicas em cada array sobre cada elemento e sua posição nos outros arrays.

A cascata fracionária foi originalmente desenvolvida para resolver com eficiência vários problemas de geometria computacional . O cascateamento fracionário foi aplicado em outros lugares, como em mineração de dados e roteamento de protocolo da Internet .

Generalização para gráficos

A pesquisa binária foi generalizada para trabalhar em certos tipos de gráficos, onde o valor de destino é armazenado em um vértice em vez de um elemento de matriz. Árvores de pesquisa binárias são uma dessas generalizações - quando um vértice (nó) na árvore é consultado, o algoritmo aprende que o vértice é o alvo ou, de outra forma, em qual subárvore o alvo estaria localizado. No entanto, isso pode ser mais generalizado como segue: dado um gráfico não direcionado, positivamente ponderado e um vértice alvo, o algoritmo aprende ao consultar um vértice que ele é igual ao alvo, ou recebe uma borda de incidente que está no caminho mais curto do vértice consultado ao alvo. O algoritmo de pesquisa binária padrão é simplesmente o caso em que o gráfico é um caminho. Da mesma forma, as árvores de busca binárias são o caso em que as arestas das subárvores à esquerda ou à direita são fornecidas quando o vértice consultado é diferente do alvo. Para todos os gráficos não direcionados e positivamente ponderados, existe um algoritmo que encontra o vértice alvo nas consultas no pior caso.

Pesquisa binária barulhenta

Na pesquisa binária barulhenta, existe uma certa probabilidade de que a comparação esteja incorreta.

Os algoritmos de busca binária barulhenta resolvem o caso em que o algoritmo não pode comparar de forma confiável os elementos da matriz. Para cada par de elementos, há uma certa probabilidade de que o algoritmo faça a comparação errada. A busca binária ruidosa pode encontrar a posição correta do alvo com uma determinada probabilidade que controla a confiabilidade da posição produzida. Todo procedimento de busca binária ruidoso deve fazer pelo menos comparações em média, onde é a função de entropia binária e é a probabilidade de que o procedimento produza a posição errada. O ruidoso problema da busca binária pode ser considerado um caso do jogo Rényi-Ulam , uma variante das Vinte Perguntas em que as respostas podem estar erradas.

Pesquisa binária quântica

Os computadores clássicos são limitados ao pior caso de iterações exatas ao realizar a pesquisa binária. Os algoritmos quânticos para pesquisa binária ainda estão limitados a uma proporção de consultas (representando iterações do procedimento clássico), mas o fator constante é menor que um, proporcionando uma complexidade de tempo menor em computadores quânticos . Qualquer procedimento de pesquisa binária quântica exata - isto é, um procedimento que sempre produz o resultado correto - requer pelo menos consultas no pior caso, onde está o logaritmo natural . Existe um procedimento de pesquisa binária quântica exata que é executado em consultas no pior caso. Em comparação, o algoritmo de Grover é o algoritmo quântico ideal para pesquisar uma lista não ordenada de elementos e requer consultas.

História

A ideia de classificar uma lista de itens para permitir uma pesquisa mais rápida remonta à antiguidade. O primeiro exemplo conhecido foi a tabuinha Inakibit-Anu da Babilônia que data de c.  200 AC . A tabuinha continha cerca de 500 números sexagesimais e seus recíprocos classificados em ordem lexicográfica , o que tornava a busca por uma entrada específica mais fácil. Além disso, várias listas de nomes classificados pela primeira letra foram descobertas nas ilhas do Egeu . Catholicon , um dicionário latino concluído em 1286 EC, foi a primeira obra a descrever regras para classificar palavras em ordem alfabética, em oposição a apenas as primeiras letras.

Em 1946, John Mauchly fez a primeira menção à busca binária como parte das Moore School Lectures , um curso universitário seminal e fundamental em computação. Em 1957, William Wesley Peterson publicou o primeiro método de pesquisa de interpolação. Cada algoritmo de pesquisa binária publicado funcionou apenas para matrizes cujo comprimento é um a menos do que uma potência de dois até 1960, quando Derrick Henry Lehmer publicou um algoritmo de pesquisa binária que funcionou em todas as matrizes. Em 1962, Hermann Bottenbruch apresentou uma implementação ALGOL 60 de busca binária que colocava a comparação por igualdade no final , aumentando o número médio de iterações em um, mas reduzindo para um o número de comparações por iteração. A busca binária uniforme foi desenvolvida por AK Chandra da Universidade de Stanford em 1971. Em 1986, Bernard Chazelle e Leonidas J. Guibas introduziram a cascata fracionária como um método para resolver vários problemas de busca em geometria computacional .

Problemas de implementação

Embora a ideia básica da pesquisa binária seja comparativamente direta, os detalhes podem ser surpreendentemente complicados

Quando Jon Bentley atribuiu a pesquisa binária como um problema em um curso para programadores profissionais, ele descobriu que noventa por cento falhou em fornecer uma solução correta após várias horas de trabalho nisso, principalmente porque as implementações incorretas não funcionaram ou retornaram uma resposta errada em raras casos extremos . Um estudo publicado em 1988 mostra que um código preciso para ele só é encontrado em cinco entre vinte livros didáticos. Além disso, a própria implementação de busca binária de Bentley, publicada em seu livro de 1986, Programming Pearls , continha um erro de estouro que permaneceu não detectado por mais de vinte anos. A implementação da biblioteca da linguagem de programação Java da pesquisa binária teve o mesmo bug de estouro por mais de nove anos.

Em uma implementação prática, as variáveis ​​usadas para representar os índices frequentemente serão de tamanho fixo (inteiros), e isso pode resultar em um estouro aritmético para matrizes muito grandes. Se o ponto médio do intervalo for calculado como , então o valor de pode exceder a faixa de inteiros do tipo de dados usado para armazenar o ponto médio, mesmo se e estiverem dentro da faixa. Se e não forem negativos, isso pode ser evitado calculando o ponto médio como .

Um loop infinito pode ocorrer se as condições de saída para o loop não forem definidas corretamente. Uma vez excedido , a pesquisa falhou e deve transmitir o fracasso da pesquisa. Além disso, o loop deve ser encerrado quando o elemento de destino for encontrado ou, no caso de uma implementação em que essa verificação seja movida para o final, deve-se verificar se a pesquisa foi bem-sucedida ou falhou no final. Bentley descobriu que a maioria dos programadores que implementaram incorretamente a pesquisa binária cometeram um erro ao definir as condições de saída.

Suporte de biblioteca

As bibliotecas padrão de muitas linguagens incluem rotinas de pesquisa binárias:

  • C fornece a função bsearch() em sua biblioteca padrão , que normalmente é implementada por meio de pesquisa binária, embora o padrão oficial não exija isso.
  • C ++ 's Standard Template Library fornece as funções binary_search(), lower_bound(), upper_bound()e equal_range().
  • D biblioteca padrão de Phobos, no std.rangemódulo fornece um tipo SortedRange(retornado por sort()e assumeSorted()funções) com métodos contains(), equaleRange(), lowerBound()e trisect(), que utilizam técnicas de busca binária por padrão para as faixas que oferecem acesso aleatório.
  • COBOL fornece o SEARCH ALLverbo para realizar pesquisas binárias em tabelas ordenadas COBOL.
  • Go 's sortpacote de biblioteca padrão contém as funções Search, SearchInts, SearchFloat64se SearchStrings, que implementam busca binária geral, bem como implementações específicas para pesquisar fatias de inteiros, números de ponto flutuante e strings, respectivamente.
  • Java oferece um conjunto de métodos estáticos sobrecarregados binarySearch() nas classes Arrayse Collectionsno java.utilpacote padrão para realizar pesquisas binárias em arrays Java e em Lists, respectivamente.
  • Microsoft 's .NET Framework 2.0 oferece estáticos genéricos versões do algoritmo de busca binária em suas classes coleção de base. Um exemplo seria System.Arrayo método de BinarySearch<T>(T[] array, T value).
  • Para Objective-C , a estrutura Cocoa fornece o NSArray -indexOfObject:inSortedRange:options:usingComparator:método no Mac OS X 10.6+. O framework Core Foundation C da Apple também contém uma CFArrayBSearchValues()função.
  • Python fornece o bisectmódulo.
  • A classe Array do Ruby inclui um bsearchmétodo com correspondência aproximada embutida.

Veja também

Notas e referências

Este artigo foi submetido ao WikiJournal of Science para revisão por pares acadêmicos externos em 2018 ( relatórios do revisor ). O conteúdo atualizado foi reintegrado na página da Wikipedia sob uma licença CC-BY-SA-3.0 ( 2019 ). A versão do registro revisada é: Anthony Lin; et al. (2 de julho de 2019). "Algoritmo de pesquisa binária" (PDF) . WikiJournal of Science . 2 (1): 5. doi : 10.15347 / WJS / 2019.005 . ISSN  2470-6345 . Wikidata  Q81434400 .

Notas

Citações

Fontes

links externos