Я вижу, что ваше текущее решение - это простой линейный поиск, который вы правильно называете O (n) (не O (1), поскольку это только один изолированный случай с вероятностью 1 / n).
Лучшим решением для поиска числа в отсортированном массиве чисел было бы использование двоичного поиска. (Даже если ваш массив не отсортирован, если вы выполняете значительное количество поисков, возможно, стоит отсортировать ваши числа с помощью сортировки по O (n), например, по радикальной сортировке, а затем продолжить выполнение двоичного поиска на вашем отсортированный массив)
Концепция бинарного поиска состоит в том, чтобы постоянно сравнивать средние элементы массивов с целевым значением и рекурсивно искать половину тока, который будет содержать целевой элемент, возвращая, если значение найдено в любой точке.
Постоянно отбрасывая половины массивов, которые не могут содержать целевое значение, бинарный поиск имеет временную сложность O (log n), что значительно лучше, чем O (n).
Вот отличный ресурс для этого:
https://www.geeksforgeeks.org/binary-search/
Удачи!