Binary Search //JavaScript Repository

Description

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

Code (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;
};

Example (Example)

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

Help

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

Rank (Votes: 68)

2.87