Elmord's Magic Valley

Software, lingüística e rock'n'roll. Às vezes em Português, sometimes in English.

Pesquisa binária malandra

2012-04-06 00:06 -0300. Tags: comp, prog, em-portugues

A pesquisa binária clássica procura por um elemento em uma lista que "case" com um dado item, aproveitando-se do fato de que a lista está ordenada. O "casamento" pode ser dado por um teste de igualdade, ou por uma comparação por um campo do elemento, ou outras possibilidades. O ponto importante é que o elemento desejado "compara igual" com o item, todos os elementos anteriores "comparam menor" com o item e todos os elementos posteriores "comparam maior" com o item.

Mas esse não é o único tipo de pesquisa binária possível. Ao invés de casarmos os elementos da lista com um item, podemos guiar a pesquisa por um predicado que é verdadeiro para todos os elementos a partir de um dado ponto na lista, e falso para todos os elementos anteriores. Não há sequer o requerimento de ordem na lista; apenas que o predicado particione a lista em dois segmentos contíguos. A pesquisa então retorna o índice do primeiro elemento para o qual o predicado é verdadeiro:

function malandrous_binary_search(cmp, item, list) {
    // Retorna o índice do primeiro elemento da lista para o qual   
    // cmp(elem, item) é verdadeiro. [Uma definição alternativa seria
    // passar um predicado de um argumento só e não passar 'item'.]

    var min=0, max=list.length, mid;

    while (min != max) {
        mid = Math.floor((min+max)/2);
        if (cmp(list[mid], item))
            max = mid;       // Se list[mid] satisfaz o teste, então a posição
                             // que queremos é mid ou está antes de mid.
        else
            min = mid + 1;   // Se list[mid] não satisfaz o teste, então o que
                             // queremos só pode estar depois de mid.
    }
    return min;
}

// Exemplo.
fives_start = malandrous_binary_search(function(x,y) x>=y, 5, [1,1,2,3,5,5,5,8,13,13,21]);
fives_end   = malandrous_binary_search(function(x,y) x>y,  5, [1,1,2,3,5,5,5,8,13,13,21]);

Eu denomino este algoritmo pesquisa binária malandra.

A primeira (e única) vez em que me deparei com esta maravilha foi no código do mwetoolkit, no qual eu estava trabalhando ano passado como bolsista. Lá, a pesquisa binária malandra é usada para encontrar um range de frases ordenadas que começam com um mesmo prefixo. Para isso, procura-se o primeiro elemento da lista que seja maior ou igual ao prefixo (onde um elemento é "igual" ao prefixo se inicia com ele), e o primeiro elemento que seja maior (i.e., o primeiro elemento fora do range). [Na verdade, a pesquisa é feita sobre todos os sufixos de um texto, usando uma array de sufixos, outra invenção especial de primeira que descobri lá. Até que eu aprendi com essa bolsa, vou lhes contar.]

Comentários / Comments (0)

Deixe um comentário / Leave a comment

Main menu

Posts recentes

Comentários recentes

Tags

em-portugues (213) comp (137) prog (68) in-english (50) life (47) pldesign (35) unix (34) lang (32) random (28) about (27) mind (25) lisp (23) mundane (22) fenius (20) ramble (17) web (17) img (13) rant (12) hel (12) privacy (10) scheme (10) freedom (8) copyright (7) bash (7) music (7) academia (7) lash (7) esperanto (7) home (6) mestrado (6) shell (6) conlang (5) emacs (5) misc (5) latex (4) editor (4) book (4) php (4) worldly (4) android (4) politics (4) etymology (4) wrong (3) security (3) tour-de-scheme (3) kbd (3) c (3) film (3) network (3) cook (2) poem (2) physics (2) wm (2) treta (2) philosophy (2) comic (2) lows (2) llvm (2) perl (1) en-esperanto (1) audio (1) old-chinese (1) kindle (1) german (1) pointless (1) translation (1)

Elsewhere

Quod vide


Copyright © 2010-2020 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.

Powered by Blognir.