Как найти объект в массиве по свойству?

Question

[Алексей]

Дан массив объектов. Необходимо найти индекс объекта в массиве по значению свойства. За условие берем что для каждого объекта свойство уникально.

var searchId = 5;
var arr = [{  id : 1 },{ id : 7 },{ id : 5 }];

Как тут получить индекс 3?

Предвидя решения с циклом for ( и соответственно другие переборы ) хотелось узнать насколько производителен этот метод при больших массивах ( 100k+ элементов ).
Ну и само собой есть ли другие варианты поиска и насколько они производительнее?

Answer 1

[Сергей Протько]

Вопервых индес будет 2 а не 3
Во вторых так как данные у вас не отсортированы, сложность алгоритма поиска в любом случае будет O(N).
В третьих если бы данные были отсортированы по этому ключу, можно было бы применить бинарный поиск у которого сложность будет O(1 +logN). Есть еще интерполяционный поиск со сложностью O(log(log(N)) но опять же работает только с отсортированными массивами.
Ну и последнее, 100К+ элементов это не так много.

Все три метода: jsfiddle.net/op1jxpsm/2 на массиве из 10 000 000 элементов
Результаты:

Хороший для тупого перебора случай, ищем 12415
Basic search: average=0ms, min = 0ms, max = 2ms
Binary search: average=0ms, min = 0ms, max = 0ms
Interpolation search: average=0ms, min = 0ms, max = 0ms

Средний для перебора случай, ищем 3451524:
Basic search: average=64ms, min = 62ms, max = 67ms
Binary search: average=0ms, min = 0ms, max = 0ms
Interpolation search: average=0ms, min = 0ms, max = 0ms

Плохой для перебора случай, ищем 9542417:
Basic search: average=176ms, min = 158ms, max = 182ms
Binary search: average=0ms, min = 0ms, max = 0ms
Interpolation search: average=0ms, min = 0ms, max = 0ms