Вы неверно понимаете суть О-нотации. Почитайте книги Дональда Кнута про это.
O(3) - это то же самое, что O(1). Нет разницы. O(N), O(N+1000), O(10*N) - это тоже одно и то же.
В таких случаях речь всегда идёт не про конкретный кейс, а про обобщенный. Вы не знаете в каком порядке элементы вашего массива, где находится искомый, сколько всего элементов будет в конкретных кейсах, поэтому определяется ряд случаев: средний (по вероятности, если входные данные рандомные), худший (чтобы понимать границы и сколько может "висеть" алгоритм теоретически). Лучшие варианты обычно никого не интересуют, потому что и вероятность их мала, и смысла никакого нет в столь малых величинах.
У вас типичный случай компромисса в реализации структуры данных. Вы всегда балансируете между памятью и скоростью. Больших семь шапок из овцы не выкроить никак.
То есть, вы можете сделать такую структуру данных, которая "под капотом" будет держать древовидный индекс с данными или отсортированную по ключу карту значений для бинарного поиска. Хотя эти варианты - суть одно и то же.
Если не рассматривается вариант размена производительности на память, то в этой задаче у вас будет только O(N) без вариантов.
Если усложнить структуру данных, то можно добиться и O(logN) при поиске, и даже O(1). Почитайте как устроен словарь в питоне.
Да, помимо сложности поиска у вас будет сложность вставки в структуру новых элементов. И тут опять трейд-офф. Ну а что вы хотели?
