Какая сложность поиска элемента по значению в массиве?

Question

Поиск элемента по значению в PHP-массиве имеет линейную сложность. PHP должен проверить каждый элемент. Это медленнее, чем поиск по ключу. Для частого поиска по значению стоит менять структуру данных.

YeaHub · Accepted Answer

Когда мы ищем элемент по значению, PHP не может использовать хеш-таблицу напрямую.Почему поиск по значению медленныйХеш-таблица оптимизирована для поиска по ключу, но:Значения не индексируютсяНет быстрого доступа к нужному значениюПоэтому PHP вынужден проходить массив целиком.Пример поискаin_array('apple', $fruits);
Или:array_search('apple', $fruits);
Сложность операцииЛучший случай: O(1) (если элемент первый)Средний и худший случай: O(n)Как оптимизироватьИспользовать значения как ключиПредварительно строить индексМенять структуру данных$map = [
    'apple' => true,
    'banana' => true,
];
Где это важноФильтрация больших массивовПроверки в циклахВысоконагруженные участки кодаКраткий выводПоиск по значению всегда дорогой. Если он выполняется часто — структуру данных стоит пересмотреть.