Использует ли in_array () алгоритм двоичного поиска?

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

Я использую in_array(), но подозреваю, что он выполняет простой цикл - кто-нибудь знает, использует ли алгоритм in_array() алгоритм bsearch?


php binary-search bsearch
person morpheous    schedule 13.05.2010    source источник
comment
Не уверен, что это делает in_array. Я наткнулся на это, подумал, может быть, вам это пригодится. au.php.net/manual/en/function.array- search.php # 93352   -  person Russell Dias    schedule 13.05.2010

Ответы (3)


arrow_upward
11
arrow_downward

in_array() - это O(n). Также см. Список Big-O для функций PHP

person ThiefMaster    schedule 13.05.2010

arrow_upward
5
arrow_downward

Поскольку для этого не требуется сортировка массива, я не понимаю, как он может выполнять двоичный поиск.

person nc3b    schedule 13.05.2010
comment
Я знаю, что это не так, но, честно говоря, OP, возможно, подумал, что PHP поддерживает порядок сортировки под капотом. - person Jordan Arseno; 29.05.2013

arrow_upward
4
arrow_downward

in_array() использует линейный (O (n)) поиск, а не двоичный (O (log n)) поиск.

Если вы хотите O (log n) или лучше, я бы предложил вам либо поместить значения, которые вы хотите искать, в качестве ключей в массиве, либо создать структуру индекса, которая эффективно делает то же самое.

person cletus    schedule 13.05.2010