Быстрый поиск объектов
 

Есть такая задача:
Множество объектов. Каждый объект имеет числовой ключ (вещественный).
Нужна функция, которая позволяет определить по заданному числовому значению список объектов, ключ которых больше/меньше заданного числа.
Самое простое, что приходит в голову, это, конечно, взять массив объектов и отсортировать по ключу. Тогда очень просто найти нужные объекты. Но дело в том, что объекты добавляются не все сразу, а по одному. Т.е. при вставке нового объекта нужно изменять массив. А это операция вроде не самая быстрая (по крайней мере для того же С++).

Ещё есть идея с бинарными деревьями. Но прежде чем копать, рушеил поинтересоваться у спецов javascript: может есть какие-то библиотеки для решения такой задачи? Или может вставка нового элемента в середину массива на javascript операция быстрая?

P.S. Количество объектов теоретически от 0 до много. :) Это решение буду прикручивать к google и яндекс map. И каждый объект - это метка на карте. К примеру пользователь может добавить на карту ВСЕ дома города Москвы. С учетом наличия около 4500 улиц количество домов может быть весьма приличным.

Зависит от массива, потестируйте на вашем случае.

Тестировать нужно на IE, FF, Opera (как минимум), потому и спрашиваю у гуру, чтобы время съэкономить. Размер массива в 50-150 тысяч объектов меня почему-то сразу наводит на мысль, что будет тормозить. :)
Хотя, на таких объемах при добавлении по одному объекту наверное всё-равно будет тормозить. Так то по-любому нужно будет делать пакетное добавление.

Как показали тесты никаких хитрых алгоритмов не требуется, так как скорость прогонки проверки в цикле достаточно большая. Такой код:

//------------------------------------
 id = "init";
 console.time(id);
 var arr = new Array(100000);
 for(var i=0;i<arr.length;i++)
  arr[i] = Math.random()*100;
 console.timeEnd(id);
 //------------------------------------
 id = "if/else";
 console.time(id);
 for(var i=0;i<arr.length;i++)
  if(arr[i]>0)
//   for(var j=0;j<10;j++)
    arr[i] += 1;
 console.timeEnd(id);

Время выполнения:

если индексы без пропусков, то slice

Решение найдено. Никакой вставки вообще делать не буду, так как простой перебор дает приличную скорость. При этом скорость добавления вообще супер-пупер-быстрая (просто push в конец массива)

Хотя, был удивлен тем, что конструкция вида

for(var i=0;i<arr.length;i++)

работает быстрее

for(var i in arr)

Почему-то всегда считал, что in быстрее цикла работает. Но при тесте в FF получил 50ms против 125ms

Это в принципе объяснимо, for-in перебирает все свойства объекта (у массивов много других свойств, в том числе методы) и проверяет у них свойство enumerable, в то время как for сразу берет только нужные. Ну это чисто интуитивно.

...