Busca Binária //Repositório JavaScript

Descrição

Busca um valor em um vetor ordenado utilizando busca binária ou fornece o índice onde o valor procurado deveria ser inserido para manter o vetor ordenado.
Criado: 2005.11.04 - Modificado 2005.11.19

Código (Download)

//+ Carlos R. L. Rodrigues
//@ http://jsfromhell.com/array/search [rev. #2]

search = function(o, v, i){
    var h = o.length, l = -1, m;
    while(h - l > 1)
        if(o[m = h + l >> 1] < v) l = m;
        else h = m;
    return o[h] != v ? i ? h : -1 : h;
};

Exemplo (Exemplo)

<script type="text/javascript">
//<![CDATA[

//cria um vetor "a" com 20 elementos
for(var a = [], i = 20; i; a[--i] = i * 10 + i);

document.write(
    "A = ", a, "<br />",
    "search(A, 88) = ", search(a, 88), "<br />",
    "search(A, 50) = ", search(a, 50), "<br />",
    //Retorna o ?nd?ce onde o 45 deve ser inserido para manter a ordem do vetor
    "search(A, 45, true) = ", search(a, 45, true)
);

//]]>
</script>

Ajuda

search(vetor: Array, value: Object, [insert: Boolean = false]): Integer
Efetua a busca em um vetor *ordenado*, se ele não estiver ordenado, o comportamento é indeterminado. A função pode retornar tanto a posição do objeto procurado, quanto a posição onde ele deveria ser inserido para manter a ordenação no vetor.
vetor
array onde será realizada a busca
value
objeto a ser procurado dentro do vetor
insert
se true, a função retornará a posição onde o valor deve ser inserido para que o array permaneça ordenado, caso contrário retorna a posição onde o elemento se encontra ou -1 caso ele não seja encontrado

Ranque (Votos: 46)

3.33