English : Português

Description : Code : Example : Help : Rank

Searches a value inside an ordered array using binary search or supplies the index where the searched value should be inserted to keep the array ordered.
Created: 2005.11.04 - Modified 2005.11.19

//+ 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;
};

<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>

search(vector: Array, value: Object, [insert: Boolean = false]): Integer

Do a binary search on an *ordered* array, if it's not ordered, the behaviour is undefined. The function can return the index of the searched object as well the the index where it should be inserted to keep the array ordered.

vector

array that will be looked up

value

object that will be searched

insert

if true, the function will return the index where the value should be inserted to keep the array ordered, otherwise returns the index where the value was found or -1 if it wasn't found

0 1 2 3 4 5