Самый быстрый способ поиска элемента в несортированном массиве

Я только что наткнулся на этот вопрос сегодня и пытался найти решение, которое лучше, чем O (N), но не смог его придумать.

Поискал в SO, но не смог найти этот вопрос.

Есть ли какое-нибудь решение лучше, чем O (n), или это проблема, которую нельзя решить лучше, чем это?

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

Я пытался найти решение на C ++, но без JavaScript IndexOf (), C # Array.find () или LINQ.