Array search NP completeness
If you want to prove that a problem is NP-complete, you don't get to make up your own definition of NP. NP is the class of problems that can be solved by a nondeterministic Turing machine in time bounded by some polynomial function of the length of the input.

Specifically, you don't get to use oracles, you don't get to use some other measure of the size of the input (e.g., the logarithm of its length) and you don't get to make random access to the  contents array: you have to walk the head of the Turing machine there, one cell at a time.

Your problem is, as you say in your first sentence, clearly in P. It is, therefore, very unlikely to be NP-complete, since that can only happen if P=NP.